Cs.umanitoba.ca

CCCG 2010, Winnipeg MB, August 9–11, 2010 Some Properties of Higher Order Delaunay and Gabriel Graphs the segment pipj with both pi and pj on its boundarycontains at most k points from S different from pi, pj.
We consider two classes of higher order proximity graphs The standard Gabriel graph corresponds to 0-GG(S) defined on a set of points in the plane, namely, the k-Delaunay graph and the k-Gabriel graph. We give The combinatorial and geometric properties of these bounds on the following combinatorial and geometric graphs have been widely studied for the case k = 0 properties of these graphs: spanning ratio, diameter, (see [10]). However, not so much is known for higher chromatic number, and minimum number of layers nec- values of k. Some results are given in [1, 16], but the essary to partition the edges of the graphs so that no topic has still not been explored in full depth; a system- atic study is being developed in [15].
The first property considered in this paper is the spanning ratio, a parameter capturing to what extent Let S be a set of n points in the plane in general posi- traveling along a graph is much longer than traveling tion (no three are collinear and no four are concyclic).
along the plane (the formal definition is given below).
A proximity graph on S is a geometric graph where two For k = 0, the spanning ratio of several proximity points are adjacent if they satisfy some specific proxim- graphs has been studied in the literature [5, 6, 9, 11], ity criterion. Proximity graphs have been widely studied and determining the exact value of the spanning ratio of due to their theoretical interest and to their applications the Delaunay triangulation remains a challenging open in situations where it is necessary to extract the “shape” problem. Our main goal here is to study the relationship of a set of points (see [10] for a survey).
Adjacency in many proximity graphs is defined in We also study the diameter of k-DG(S) and k-GG(S), terms of an empty region associated to any pair of which can be seen as a combinatorial counterpart to the points. To provide more flexibility the definition of the graphs can be relaxed to allow up to k points to lie inthe neighborhood region. This gives rise to higher order Finally, we give bounds on the minimum number of proximity graphs. In this paper we deal with two such layers necessary to partition the edges of k-DG(S) or k-GG(S) so that no two edges of the same layer cross.
We consider the k-Delaunay graph of S (denoted From a theoretical point of view, this is related to a k-DG(S)), where a straight-line segment connects points more general problem that remains unsolved (see, for example, [4, 12]): for every geometric graph G with at i, pj ∈ S if there exists a circle C (pi, pj ) through pi and most λ pairwise crossing edges, can the edges of G can j with at most k points of S in its interior. The stan- dard Delaunay triangulation corresponds to 0-DG(S) be colored with f (λ) colors such that crossing edges receive distinct colors? In our particular case, the an- We also study the k-Gabriel graph of S (denoted by swer is affirmative, as it can be shown that the graphs k-GG(S)), where a straight-line segment connects points k-GG(S) and k-DG(S) contain at most 2k + 1 pairwise crossing edges. In Section 6 we give a quadratic upper i, pj ∈ S if the closed disk centered at the midpoint of bound on the number of colors required.
From a more practical point of view, DT(S) and †Computer Science Department, Universit´e Libre de Bruxelles, GG(S) satisfy some properties that make them interest- {secollet,mkormanc,slanger}@ulb.ac.be. Supported by A.R.C.
ing in the context of routing in wireless networks [7, 13].
Finding ways to extract plane layers from k-DG(S) or ‡Departament de Matem`atica Aplicada II, Universitat k-GG(S) may have applications in this setting.
MTM2009-07242 and Gen. Cat. DGR 2009SGR1040.
§Charg´e de recherches du F.R.S.-FNRS.
¶Maˆıtre de recherches du F.R.S.-FNRS.
(k + 1)-GG(S), (iii) k-GG(S) ⊆ k-DG(S).
22nd Canadian Conference on Computational Geometry, 2010 Proof. The first part follows from a result in [5] statingthat the spanning ratio of the 0-Gabriel graph of any n- Let G be a geometric graph on S and P = {p1p2 · · · pl} be a path in G. We define the geometric length of P as As for the second part, consider the Gabriel graph ipi+1|, where |pipj | is the Euclidean distance be- tween pi and pj. The geometric distance between points pi, pj ∈ S, denoted by dg(pi, pj), is the minimum over the geometric length of all paths in G connecting pi and out changing the combinatorial structure of the graph.
pj. The spanning ratio of G is defined as Now, proceeding as in the proof of Theorem 1, we ob-tain a point set whose k-Gabriel graph has spanning The number of edges of k-Delaunay graphs grows with k. Consequently, it would be reasonable to believe We define the combinatorial length of a path P on a ge- that the spanning ratio of these graphs decreases as k ometric graph G as the number of its edges. The combi- increases. Surprisingly, the next theorem shows that in the worst case the spanning ratio of k-DG is not smaller than the spanning ratio of the Delaunay triangulation.
c(pi, pj ), is the minimum over the combinatorial length of all paths in G connecting pi and pj. The diameter ofG, denoted by D(G), is defined as the maximum over Theorem 1 For any set S of n points in the plane, any the combinatorial distance of all pairs of points in S.
points S such that SR(k-DG(S )) ≥ SR(DT(S)) − .
Theorem 3 Let S be a set of n points in the plane andk ≤ n/2 − 1. Let i be the integer such that n/2i+1 − Proof. Consider the Delaunay triangulation of S.
1 ≤ k < n/2i − 1. Then D(k-DG(S)) ≤ 2i. There Since S is in general position, the combinatorial struc- exist sets of n points in the plane whose k-Delaunay ture of the graph does not change when moving each Proof. It suffices to prove the upper bound for values property is called the tolerance of DT(S) and is denoted of k of the form k = n/2i+1 − 1. We use induction For i = 0, we want to prove that ( n − 1)-DG(S) has diameter 1, i.e., is the complete graph. Let pj and pl be two points in S. The line passing through pj and pl divides the plane into two open half-planes, one ofwhich contains at most n/2 − 1 points in S. It is easy > 0, for each pl ∈ S, define pl,0 = pl and place to see that there exists a circle through pj and pl that k new points pl,1, pl,2, . . . , pl,k at distance from pl,0 less does not contain any point in S lying on the opposite than min{tol (DT(S)), pipj| }. Let S be the resulting half-plane. This circle contains no more than n/2 − 1 set of points. By construction, if pl and pm are not points of S in its interior, hence pj and pl are adjacent adjacent in DT(S), then pl,ν and pm,ι are not adjacent in k-DG(S ) for any ν, ι ∈ {0, 1, . . . , k}. Therefore, in Now assume that the result holds for some fixed i.
pj and pl with combinatorial length at most 2i. Let through pa and pb whose interior contains no morethan n/2i+1 − 1 points of S. If C contains at most n/2i+2 −1 points of S in its interior, then (pa, pb) is an For k-Gabriel graphs we provide the following the interior of C and ν ∈ {a, b}, define Cν,m as the circletangent to C at point pν containing pm on its boundary.
Theorem 2 For any set S of n points in the plane and Either there exists a point pm in the interior of C such k ≤ n − 2, the spanning ratio of k-GG(S) is O( n).
that Ca,m contains n/2i+2 − 1 points of S in its inte- There exist sets of n points in the plane whose k-Gabriel rior, or there exist two points pm, pm in the interior of C such that Ca,m = Ca,m contain n/2i+2 − 2 points CCCG 2010, Winnipeg MB, August 9–11, 2010 of S in their interior. Here we deal with the first case; the second case is analogous. Let C1 = Ca,m, wherep A j-coloring of a graph G = (V, E) is a mapping f : V → {1, 2, . . . , j} such that f (v) = f (w) for every edge the only point of S in the intersection of C (v, w) of G. The chromatic number of G, denoted by χ(G), is the minimum j such that G is j-colorable.
Since the main result in Section 6 is given in terms of the chromatic number of k-DG(S), we provide an upper is minimum. Then the only points of S in the intersec- Theorem 5 For any set S of n points in the plane and tion of C1 and Cb,m are pm and possibly another point k ≤ n/2 − 1, χ(k-GG(S)) ≤ χ(k-DG(S)) ≤ 6(k + 1).
in the boundary of Cb,m . Thus (pa, pm ) and (pm , pb)are edges in ( Proof. The number of edges of k-DG(S) does not ex- ceed 3(k + 1)n − 3(k + 1)(k + 2) [1]. Consequently, the graph contains a vertex of degree at most 6k+5. Observe i, pj ) is an edge of k-DG(S), this edge is also Therefore, in the last graph, there exists a path from pj {pl}) for any pl ∈ S (pl = pi, pj).
to pl of combinatorial length less than or equal to 2i+1.
Thus, if k-DG(S) S is an induced subgraph of k-DG(S)on n vertices, then it is a subgraph of k-DG(S it has no more than 3(k + 1)n − 3(k + 1)(k + 2) edges.
Hence we can color k-DG(S) with 6k + 6 colors applying the minimum degree greedy algorithm [8].
Next we describe a point set for which these graphs Proposition 6 For any n ≥ 3 and k ≤ n−3 , there exists a set S of n points in the plane whose k-Gabriel and k-Delaunay graphs have chromatic number at least Proof. Let S = {p1, p2, . . . , p2k+3} denote the set of The lower bound is attained by any set of vertices of a slightly perturbed regular (2k + 3)-gon.
points such that its Delaunay triangulation is a sequen- These points form a (2k + 3)-clique in k-GG(S). There- tial triangulation. As in Theorem 1, each point (except fore the chromatic number of the graph is at least 2k+3.
possibly one) can be replaced by k + 1 points so that If n > 2k + 3, it suffices to add to S additional points any two points are adjacent if and only if they belong to far from p1, . . . , p2k+3, so that the adjacencies are pre- the same cluster or their original points were adjacent.
The k-Delaunay graph of this point set has diameter Constrained geometric thickness of 1-DG(S) and1-GG(S) In general, the k-Gabriel graph has fewer edges than the k-Delaunay graph, so its diameter is usually greater: Suppose that we want to partition the edges of a ge-ometric graph G into layers in such a way that no Theorem 4 For any set S of n points in the plane and two edges of the same layer cross. We define the con- strained geometric thickness of G, denoted by θc(G), as of n points in the plane whose k-Gabriel graphs have the smallest number of necessary layers. Observe that, in contrast to the notion of geometric thickness of acombinatorial graph, when it comes to the constrained Proof. The upper bound follows from a general result geometric thickness the embedding of the graph is fixed.
on the diameter of a graph with given minimum degree In this section we give bounds on the constrained geo- (see [14]) together with the fact that the vertices of any metric thickness of 1-DG(S) and 1-GG(S).
k-Gabriel graph have degree at least k. As for the lower Let us first introduce some definitions and recall some bound, let S = {p1, . . . , pn} be a set of n points sorted by x coordinate in an infinitesimally perturbed horizon- Edges of DT(S) are said to have order 0. The edges tal line. Then k-GG(S) contains the edge (pi, pj) if and of order k ≥ 1 are those belonging to k-DG(S), but not only if |i − j| ≤ k + 1. Thus dc(p1, pn) = n−1 .
22nd Canadian Conference on Computational Geometry, 2010 Let (pi, pj) be an edge of order 1. Then (pi, pj) is an Proof. Figure 2 shows a set of 6 points whose 1-Gabriel pl) for a certain pl ∈ S. We will say that graph contains three pairwise intersecting edges. Thus (pi, pj) is generated by pl. Observe that: (i) (pi, pj) is its constrained geometric thickness is at least three. For generated by pl if and only if there exists a circle through larger values of n it suffices to add n − 6 points outside pi and pj whose interior contains pl and no other point in S; (ii) every edge of order 1 is generated by at mostone point on each side of the line determined by theedge; (iii) if (pi, pj) is generated by pl, then (pl, pi) and(pl, pj) are edges in DT(S). (See [1].) Lemma 7 [3] Let (pi, pj), (pl, pm) be two crossingedges in 1-DG(S). If both edges have order 1, then oneof them can only be generated by the endpoints of theother. If (pl, pm) has order 0 and (pi, pj) has order 1,then (pi, pj) can only be generated by pl and pm.
We now prove the main result of this section: Figure 2: Example of a set of 6 points whose 1-Gabriel Theorem 8 For any set S of n points in the plane, graph has constrained geometric thickness at least 3.
2 ≤ θc(1-DG(S)) ≤ χ(DT(S)) ≤ 4.
Proof. The graph DT(S) is maximal planar, hence Constrained geometric thickness of k-DG(S) and each edge of order 1 crosses at least one edge in DT(S).
Since the number of edges of order 1 is strictly greaterthan zero [1], at least two layers are needed.
The arguments in the preceding section are generalized We now prove the upper bound. Let f be a χ(DT(S))- in Theorem 11. First we make some observations on the coloring of the vertices of DT(S). We define a χ(DT(S))- coloring of the edges of 1-DG(S) as follows. Let (pi, pj) Let (pi, pj) be an edge of order k. Then (pi, pj) is an be an edge of 1-DG(S). If (pi, pj) has order 1 and is {p1, p2, . . . , pk}) for some {p1, . . . , pk} ∈ l, we assign it the color f (pl) (if (pi, pj ) S. We will say that (pi, pj) is generated by {p1, . . . , pk}.
is generated by two points, we arbitrarily assign one of It holds that: (i) (pi, pj) is generated by {p1, . . . , pk} if and only if there exists a circle through pi and pj whose it an arbitrary color different from f (pi) and f (pj).
interior contains p1, . . . , pk and no other point in S; (ii) Next we prove that each color class is plane.
if (pi, pj) is generated by {p1, . . . , pk}, then (pν, pi) and (pν , pj) are edges in (k − 1)-DG(S) for all ν ∈ {1, . . . , k}.
edges of order 1. By Lemma 7, one of them can only be generated by the endpoints of the other. Let us assume Theorem 11 For any set S of n points in the plane that this is the case of edge (pi, pj). Then (pi, pj) has l) or f (pm). Since the points generating (pl, pm) are connected to both pl and pm in DT(S), their color isdifferent from f (p Proof. We define a χ2((k − 1)-DG(S)) -coloring of the edges of k-DG(S) such that within each color class no Consider a χ((k − 1)-DG(S))-vertex coloring f of i, pj ) has order 1 and (pl, pm) has order 0.
(k − 1)-DG(S). If (pi, pj) is an edge of k-DG(S), the l, pm) is different from f (pl) and f (pm).
color assigned to (pi, pj) is the tuple {f (pi), f (pj)}.
Let us prove that no two edges of the same color cross.
m. Hence its color is f (pl) or f (pm).
Suppose that (pi, pj) and (pl, pm) are two crossing edges Corollary 9 For any set S of n points in the plane, in k-DG(S), where (pi, pj) has order s and (pl, pm) has order t, with 0 ≤ s, t ≤ k. Without loss of generality, let us assume that s ≥ 1 and that the circle C(pi, pj) We now give a worst-case lower bound on the con- contains pl in its interior. Then pl is connected to pi strained geometric thickness of 1-DG(S) and 1-GG(S): and pj in the graph (s − 1)-DG(S) ⊆ (k − 1)-DG(S).
Therefore f (pl) = f (pi), f (pj).
Proposition 10 For any n ≥ 6, there exists a setS of n points in the plane such that θc(1-DG(S)) ≥ Corollary 12 For any set S of n points in the plane and k ≤ n/2 − 1, θc(k-GG(S)) ≤ θc(k-DG(S)) ≤ 18k2.
CCCG 2010, Winnipeg MB, August 9–11, 2010 Unfortunately, in this case our worst-case upper and [7] P. Bose, P. Morin, I. Stojmenovic, and J. Urrutia. Rout- lower bounds do not have the same order of magnitude: ing with guaranteed delivery in ad hoc wireless net-works. Wireless Networks, 7(6):609–616, 2001.
Proposition 13 For any n ≥ 3 and k ≤ n−3 , there [8] R. Diestel. Graph Theory. Springer-Verlag, 2005.
exists a set S of n points in the plane whose k-Gabrieland k-Delaunay graphs have thickness at least k + 1.
[9] D. P. Dobkin, S. J. Friedman, and K. J. Supowit. De- launay graphs are almost as good as complete graphs.
Proof. Consider the point set in the proof of Proposi- Discrete Comput. Geom., 5:399–407, 1990.
tion 6, with the points labelled in clockwise order. The [10] J. W. Jaromczyk and G. T. Toussaint.
edges (p1, pk+2), (p2, pk+3), . . . , (pk+1, p2k+2) belong to neighborhood graphs and their relatives. Proc. IEEE, the k-Gabriel graph and are pairwise crossing. There- fore the thickness of the graph is at least k + 1.
[11] J. M. Keil and C. A. Gutwin. Classes of graphs which approximate the complete Euclidean graph. Discrete We have studied several properties of two fundamental intervals on the plane, I: chromatic number versus girth.
Europ. J. Combinatorics, 19:103–110, 1998.
As for open problems, a natural one is to close [13] E. Kranakis, H. Singh, and J. Urrutia. Compass routing the gaps between the lower and upper bounds on on geometric networks. Proc. CCCG’99, 51–54, 1999.
the spanning ratio of k-Gabriel graphs and on the [14] J. W. Moon. On the diameter of a graph. Mich. Math.
constrained geometric thickness of k-Gabriel and k- Delaunay graphs. In both cases we are inclined to think [15] M. Saumell. On geometric proximity. Ph.D. thesis, in that the lower bounds are closer to the true values.
[16] T.-H. Su and R.-Ch. Chang. The k-Gabriel graphs and their applications. Proc. SIGAL’90, 66–75, 1990.
This research was initiated during the first UPC-ULB work- shop on Computational Geometry. We thank all participants Greg Aloupis, Victor A. Campos, Jean Cardinal, and Perouz Taslakian. We also thank Jorge Urrutia and David R. Wood for helpful comments and suggestions.
[1] M. Abellanas, P. Bose, J. Garc´ıa, F. Hurtado, C. M.
as, and P. A. Ramos. On structural and graph the- oretic properties of higher order Delaunay graphs. In-ternat. J. Comput. Geom. Appl., 19(6):595–615, 2009.
[2] M. Abellanas, F. Hurtado, and P. A. Ramos. Structural tolerance and Delaunay triangulation. Inform. Process.
Lett., 71:221–227, 1999.
M. Saumell. On crossing numbers of geometric prox-imity graphs. Manuscript, 2010. Abstract preliminaryversion in Proc. EGC’09, 151–156, 2009.
[4] G. Araujo, A. Dumitrescu, F. Hurtado, M. Noy, and J. Urrutia. On the chromatic number of some geomet-ric type Kneser graphs. Comput. Geom., 32(1):59–69,2005.
[5] P. Bose, L. Devroye, W. Evans, and D. Kirkpatrick. On the spanning ratio of Gabriel graphs and β-skeletons.
SIAM J. Discrete Math., 20(2):412–427, 2006.
V. Verma. The spanning ratio of the Delaunay trian-gulation is greater than π/2. Proc. CCCG’09, 165–167,2009.

Source: http://www.cs.umanitoba.ca/~cccg2010/electronicProceedings/paper69.pdf