We solve the subgraph isomorphism problem in planar graphs in linear time, for any pattern of constant size. Our results are based on a technique of partitioning the planar graph into pieces of small tree-width, and applying dynamic programming within each piece. The same methods can be used to solve other planar graph problems including diameter, girth, induced subgraph isomorphism, and shortest paths. We also extend our techniques to other families of graphs including the graphs of bounded genus.

Any connected plane nearest neighbor graph has diameter Ω(n^1/6). This bound generalizes to Ω(n^1/3d) in any dimension d.

We used a genetic search algorithm to find sets of points with many halving lines. There are sets of 10 points with 13 halving lines, 12 points with 18 halving lines, 14 points with 22 halving lines, 16 points with 27 halving lines, and 18 points with 32 halving lines. We find a construction generalizing the 12 point configuration and show that, for any n = 3 · 2^i, there are configurations of n points with n log_4 (2n/3) = 3(i + 1)2^i-1 halving lines.

We describe algorithms for finding the k shortest paths connecting a given pair of vertices in a digraph (allowing cycles). Our algorithms output an implicit representation of the paths as an unordered set in time O(m + n log n + k). The paths can be output in order by length in total time O(m + n log n + k log k). We can also find the k paths from a given source s to each vertex in the graph, in total time O(m + n log n + kn).

Improving on a recent breakthrough of Sharir, we show how to find two circular disks of minimum radius covering a set of points in the Euclidean plane, in randomized expected time O(n log^2 n).

If a configuration of m triangles in the plane has only n points as vertices, then there must be a set of

max { [m/(2n - 5)] Ω(m^3 /(n^6 log^2 n))

triangles having a common intersection. As a consequence the number of halving planes for a three-dimensional point set is O(n^8/3 log^2/3 n). For all m and n there exist configurations of triangles in which the largest common intersection involves

max{ [m/(2n - 5)] O(m^2 /n^3)

triangles; the upper and lower bounds match for m= O(n^2). The best previous bounds were Ω(m^3 /n^ 6 log^5 n)) for intersecting triangles, and O(n^8/3 log^5/3 n) for halving planes.

We describe an efficient algorithm for maintaining a minimum spanning tree (MST) in a graph subject to a sequence of edge weight modifications. The sequence of minimum spanning trees is computed offline, after the sequence of modifications is known. The algorithm performs (log n) work per modification, where n is the number of vertices in the graph. We use our techniques to solve the offline geometric MST problem for a planar point set subject to insertions and deletions; our algorithm for this problem performs O(log^2 n) work per modification. No previous dynamic geometric MST algorithm was known.

We compute the k smallest spanning trees of a point set in the planar Euclidean metric in time O(n log n log k + k min(k, n )^1/2 log(k/n)), and in the rectilinear metrics in time O(n log n + n log log n log k + kmin(k,n)^1/2 log(k/n)). In three or four dimensions our time bound is O(n^4/3+c + k min(k, n)^1/2 log(k/n)), and in higher dimensions the bound is O(n^2-2([d/2]+1)+c + kn^1/2 log n).