Narrow Results

We consider the problem of augmenting an $n$-vertex graph embedded in a metric space, by inserting one additional edge in order to minimize the diameter of the resulting graph. We present exact algorithms for the cases when (i) the input graph is a path, running in $O(n{log}^{3}n)$ time, and (ii) the input graph is a tree, running in $O(n^{2}logn)$ time. We also present an algorithm for paths that computes a $(1+𝜀)$-approximation in $O(n+1/{𝜀}^3)$ time.

Given a set P of n points in the plane, the order-k Delaunay graph is a graph with vertex set P and an edge exists between two points p, q ∈ P when there is a circle through p and q with at most k other points of P in its interior. We provide upper and lower bounds on the number of edges in an order-k Delaunay graph. We study the combinatorial structure of the set of triangulations that can be constructed with edges of this graph. Furthermore, we show that the order-k Delaunay graph is connected under the flip operation when k ≤ 1 but not necessarily connected for other values of k. If P is in convex position then the order-k Delaunay graph is connected for all k ≥ 0. We show that the order-k Gabriel graph, a subgraph of the order-k Delaunay graph, is Hamiltonian for k ≥ 15. Finally, the order-k Delaunay graph can be used to efficiently solve a coloring problem with applications to frequency assignments in cellular networks.

Graph-theoretic properties of certain proximity graphs defined on planar point sets are investigated. We first consider some of the most common proximity graphs of the family of the Delaunay graph, and study their number of edges, minimum and maximum degree, clique number, and chromatic number. In the second part of the paper we focus on the higher order versions of some of these graphs and give bounds on the same parameters.

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.

In this paper, we study the problem of designing robust algorithms for computing the minimum spanning tree, the nearest neighbor graph, and the relative neighborhood graph of a set of points in the plane, under the Euclidean metric. We use the term “robust” to denote an algorithm that can properly handle degenerate configurations of the input (such as co-circularities and collinearities) and that is not affected by errors in the flow of control due to round-off approximations. Existing asymptotically optimal algorithms that compute such graphs are either suboptimal in terms of the arithmetic precision required for the implementation, or cannot handle degeneracies, or are based on complex data structures.

We present a unified approach to the robust computation of the above graphs. The approach is a variant of the general region approach for the computation of proximity graphs based on Yao graphs, first introduced in Ref. 43 (A. C.-C. Yao, On constructing minimum spanning trees in $k$-dimensional spaces and related problems, SIAM J. Comput.11(4) (1982) 721–736). We show that a sparse supergraph of these geometric graphs can be computed in asymptotically optimal time and space, and requiring only double precision arithmetic, which is proved to be optimal. The arithmetic complexity of the approach is measured by using the notion of degree, introduced in Ref. 31 (G. Liotta, F. P. Preparata and R. Tamassia, Robust proximity queries: An illustration of degree-driven algorithm design, SIAM J. Comput.28(3) (1998) 864–889) and Ref. 3 (J. D. Boissonnat and F. P. Preparata, Robust plane sweep for intersecting segments, SIAM J. Comput.29(5) (2000) 1401–1421).

As a side effect of our results, we solve a question left open by Katajainen²⁷ (J. Katajainen, The region approach for computing relative neighborhood graphs in the $L_p$ metric, Computing40 (1987) 147–161) about the existence of a subquadratic algorithm, based on the region approach, that computes the relative neighborhood graph of a set of points $S$ in the plane under the $L_2$ metric.

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.

Let G=(V, E) be an n-vertex connected graph with positive edge weights. A subgraph G′=(V, E′) is a t-spanner of G if for all u, v∈V, the weighted distance between u and v in G′ is at most t times the weighted distance between u and v in G. We consider the problem of constructing sparse spanners. Sparseness of spanners is measured by two criteria, the size, defined as the number of edges in the spanner, and the weight, defined as the sum of the edge weights in the spanner. In this paper, we concentrate on constructing spanners of small weight.

For an arbitrary positive edge-weighted graph G, for any t>1, and any ∈>0, we show that a t-spanner of G with weight can be constructed in polynomial time. We also show that (log² n)-spanners of weight O(1) · wt(MST) can be constructed. We then consider spanners for complete graphs induced by a set of points in d-dimensional real normed space. The weight of an edge xy is the norm of the vector. We show that for these graphs, t-spanners with total weight O(log n) · wt(MST) can be constructed in polynomial time.

Several results from Combinatorial Geometry³ are detailed.