Narrow Results

Let S be a set of points in the plane. What is the minimum possible dilation of all plane graphs that contain S? Even for a set S as simple as five points evenly placed on the circle, this question seems hard to answer; it is not even clear if there exists a lower bound > 1. In this paper we provide the first upper and lower bounds for the embedding problem.

1. Each finite point set can be embedded into the vertex set of a finite triangulation of dilation ≤ 1.1247.

2. Each embedding of a closed convex curve has dilation ≥ 1.00157.

3. Let P be the plane graph that results from intersecting n infinite families of equidistant, parallel lines in general position. Then the vertex set of P has dilation .

We prove that computing a geometric minimum-dilation graph on a given set of points in the plane, using not more than a given number of edges, is an NP-hard problem, no matter if edge crossings are allowed or forbidden. We also show that the problem remains NP-hard even when a minimum-dilation tour or path is sought; not even an FPTAS exists in this case.

The stretch factor and maximum detour of a graph G embedded in a metric space measure how well G approximates the minimum complete graph containing G and the metric space, respectively. In this paper we show that computing the stretch factor of a rectilinear path in L₁ plane has a lower bound of Ω(n log n) in the algebraic computation tree model and describe a worst-case O(σn log² n) time algorithm for computing the stretch factor or maximum detour of a path embedded in the plane with a weighted fixed orientation metric defined by σ ≥ 2 vectors and a worst-case O(n log^d n) time algorithm to d ≥ 3 dimensions in L₁-metric. We generalize the algorithms to compute the stretch factor or maximum detour of trees and cycles in O(σn log^d+1 n) time. We also obtain an optimal O(n) time algorithm for computing the maximum detour of a monotone rectilinear path in L₁ plane.

We present tight bounds on the spanning ratio of a large family of ordered $\theta$-graphs. A $\theta$-graph partitions the plane around each vertex into $m$ disjoint cones, each having aperture $\theta =2\pi /m$. An ordered $\theta$-graph is constructed by inserting the vertices one by one and connecting each vertex to the closest previously-inserted vertex in each cone. We show that for any integer $k\ge 1$, ordered $\theta$-graphs with $4k+4$ cones have a tight spanning ratio of $1+2sin(\theta /2)/(cos(\theta /2)-sin(\theta /2))$. We also show that for any integer $k\ge 2$, ordered $\theta$-graphs with $4k+2$ cones have a tight spanning ratio of $1/(1-2sin(\theta /2))$. We provide lower bounds for ordered $\theta$-graphs with $4k+3$ and $4k+5$ cones. For ordered $\theta$-graphs with $4k+2$ and $4k+5$ cones these lower bounds are strictly greater than the worst case spanning ratios of their unordered counterparts. These are the first results showing that ordered $\theta$-graphs have worse spanning ratios than unordered $\theta$-graphs. Finally, we show that, unlike their unordered counterparts, the ordered $\theta$-graphs with 4, 5, and 6 cones are not spanners.

We present improved upper bounds on the spanning ratio of constrained $𝜃$-graphs with at least 6 cones and constrained Yao-graphs with 5 or at least 7 cones. Given a set of points in the plane, a Yao-graph partitions the plane around each vertex into $m$ disjoint cones, each having aperture $𝜃=2\pi /m$, and adds an edge to the closest vertex in each cone. Constrained Yao-graphs have the additional property that no edge properly intersects any of the given line segment constraints. Constrained $𝜃$-graphs are similar to constrained Yao-graphs, but use a different method to determine the closest vertex.

We present tight bounds on the spanning ratio of a large family of constrained $𝜃$-graphs. We show that constrained $𝜃$-graphs with $4k+2$ ($k\ge 1$ and integer) cones have a tight spanning ratio of $1+2sin(𝜃/2)$, where $𝜃$ is $2\pi /(4k+2)$. We also present improved upper bounds on the spanning ratio of the other families of constrained $𝜃$-graphs. These bounds match the current upper bounds in the unconstrained setting.

We also show that constrained Yao-graphs with an even number of cones ($m\ge 8$) have spanning ratio at most $1/(1-2sin(𝜃/2))$ and constrained Yao-graphs with an odd number of cones ($m\ge 5$) have spanning ratio at most $1/(1-2sin(3𝜃/8))$. As is the case with constrained $𝜃$-graphs, these bounds match the current upper bounds in the unconstrained setting, which implies that like in the unconstrained setting using more cones can make the spanning ratio worse.