Cover Contact Graphs

Cover Contact Graphs Nieves Atienza2,, Natalia de Castro2,, Carmen Cort´es2,, M. ´ Angeles Garrido2,, Clara I. Grima2,, Gregorio Hern´andez1, Alberto M´arquez2,, Auxiliadora Moreno2,,MartinN¨ollenburg3,, Jos´e Ramon Portillo2,,PedroReyes 2,,Jes´us Valenzuela2,, Maria Trinidad Villar2,, and Alexander Wolff4 1Dept. Matem´atica Aplicada, Fac. Inform´atica, Univ. Polit´ecnica de Madrid, Spain [email protected] 2Universidad de Sevilla, Spain {natienza, natalia, ccortes, vizuete, grima, almar, auxiliadora, josera, preyes, jesusv, villar}@us.es 3Fakult¨at f¨ur Informatik, Universit¨at Karlsruhe, Germany [email protected] 4Faculteit Wiskunde en Informatica, TU Eindhoven, The Netherlands http://www.win.tue.nl/~awolff Abstract. We study problems that arise in the context of covering certain geometric objects (so-called seeds, e.g., points or disks) by a set of other geometric objects (a so-called cover, e.g., a set of disks or homothetic triangles). We insist that the interiors of the seeds and the cover elements are pairwise disjoint, but they can touch. We call the contact graph of a cover a cover contact graph (CCG). We are interested in two types of tasks: (a) deciding whether a given seed set has a connected CCG, and (b) deciding whether a given graph has a realization as a CCG on a given seed set. Concerning task (a) we give efficient algorithms for the case that seeds are points and covers are disks or triangles. We show that the problem becomes NP-hard if seeds and covers are disks. Concerning task (b) we show that it is even NP-hard for point seeds and disk covers (given a fixed correspondence between vertices and seeds). 1 Introduction Koebe’s theorem [9,11], a beautiful and classical results in graph theory, says that every planar graph can be represented as a coin graph, i.e., a contact graph of disks in the plane. In other words, given any planar graph with nvertices, there is a set of ndisjoint open disks in the plane that are in one-to-one correspondence to the vertices such that a pair of disks is tangent if and only if the corresponding vertices are adjacent. Koebe’s theorem has been rediscovered several times, see the survey of Sachs [12]. Collins and Stephenson [4] give an efficient algorithm for numerically approximating the radii and locations of the disks of such a Partially supported by projects PAI FQM—0164 and ORI MTM2005-08441-C02-01.  Supported by grant WO 758/4-2 of the German Research Foundation (DFG). S.-H. Hong, T. Nishizeki, and W. Quan (Eds.): GD 2007, LNCS 4875, pp. 171–182, 2007. c Springer-Verlag Berlin Heidelberg 2007 172 N. Atienza et al. (a) disk seeds (b) disk cover of (a) (c) CCG induced by (b) Fig. 1. Seeds, cover, and CCG representation of a planar graph. Their algorithm relies on an iterative process suggested by Thurston [13]. Since Koebe there has been a lot of work in the graph-drawing community dedicated to the question which planar graphs can be represented as contact or intersections graphs of which geometric object. As a recent example, Fraysseix and Ossona de Mendez [5] showed that any four-colored planar graph without an induced four-colored C4is the intersection graph of a family of line segments. On the other hand, there has been a lot of work in the geometric-optimization community dedicated to the question how to (optimally) cover geometric objects (usually points) by other geometric objects (like convex shapes, disks, annuli). As an example take Welzl’s famous randomized algorithm [15] for finding the smallest enclosing ball of a set of points. In this paper we combine the two previous problems: we are looking for geometric objects (like disks or triangles) whose interiors are disjoint, that cover given pairwise disjoint objects called seeds (like points or disks) and at the same time represent a given graph or graph property by the way they touch each other. Other than in geometric optimization each of our covering objects contains only one of the seeds. We are not interested in maximizing the sizes of the covering objects; instead we want them to jointly fulfill some graph-theoretic property (like connectivity). Compared to previous work on geometric representation of graphs we are more restricted in the choice of our representatives. Let us get a bit more formal. Given a set Sof pairwise disjoint seeds of some type, a cover of Sis a set Cof closed objects of some type with the property that each object contains exactly one seed and that the interiors of no two objects intersect. Figure 1b depicts a disk cover of the disk seeds in Figure 1a. Now the cover contact graph (CCG) induced by Cis the contact graph of the elements of C. In other words, two vertices of a CCG are adjacent if the corresponding cover elements touch, i.e., their boundaries intersect. Figure 1c depicts the CCG induced by the cover in Figure 1b. Note that the vertices of the CCG are in one-to-one correspondence to both seeds and cover elements. We consider seeds to be topologically open (except if they are single points). Then seeds can touch each other. (Note that we require cover objects to be closed. This makes sure that a cover actually contains a point seed that lies on its boundary.) In this paper we investigate the following questions. Connectivity: Given a seed set, does it have a (1- or 2-) connected CCG? Cover Contact Graphs 173 Realizability: Given a planar graph and a set of seeds, can the given graph be realized as a CCG on the given seeds? A third type of question is treated in the long version of this article [3]: Enumeration: For a given number of vertices, how many graphs of a certain graph class can be realized as a CCG? However, we do consider in this paper an interesting restriction of the above problems where seeds and cover elements must lie in the half plane R2 +above and including the x-axis. Seeds are additionally restricted in that each must contain at least one point of the x-axis. In this restricted setting we call the contact graph of a cover a CCG+. See Figures 7b and 9 for examples. Our results. First, we consider arbitrary sets of point seeds, see Section 2. Concerning connectivity we show that we can always cover a set of point seeds using disks or using homothetic triangles such that the resulting CCG is 1- or even 2-connected. Our algorithms run in O(nlogn) expected and O(n2) worst-case time, respectively. Concerning realizability we give some necessary conditions and then show that it is NP-hard to decide whether a given graph can be realized as a disk-CCG if the correspondence between vertices and point seeds is given. Second, we consider the restriction where we are given a set Sof points on the x-axis as seeds. We show that in this case 1-connectivity is easy: we can realize Cnas a CCG on Sand there are trees that can be realized as a CCG+on S. For the case that the correspondence between seeds and vertices is given, we give an algorithm that decides in O(nlogn) time which trees can be realized as CCG+. Third, we consider disk seeds, see Section 4. We show that even deciding whether a set of disk seeds has a connected disk-CCG is NP-hard. We can only sketch proofs here. We refer the reader to the long version [3] of this paper. Related work. Abellanas et al. [1] proved that the following problem, which they call the coin placement problem, is NP-complete. Given ndisks of varying radii and npoints in the plane, is there a way to place the disks such that each disk is centered at one of the given points and no two disks overlap? Abellanas et al. [2] considered a related problem. They showed that given a set of points in the plane, it is NP-complete to decide whether there are disjoint disks centered at the points such that the contact graph of the disks is connected. Given a pair of touching (convex) cover elements, we can draw the corresponding edge in the CCG by a two-segment polygonal line that connects the incident seeds and uses the contact point of the cover elements as bend. This is a link to the problem of point-set embeddability. We say that a planar graph G is k-bend (point-set) embeddable if for any point set P⊂R2there is a one-to- one correspondence between Vand Psuch that the edges of Gcan be drawn as non-crossing polygonal lines with at most kbends. Kaufmann and Wiese [8] showed that (a) every 4-connected planar graph is 1-bend embeddable, (b) every planar graph is 2-bend embeddable, and (c) given a planar graph G=(V,E) and a set Pof npoints on a line, it is NP-complete to decide whether Ghas a 1-bend embedding that maps Vone-to-one on P. 174 N. Atienza et al. 2 The Seeds Are Points in the Plane In this section we study point seeds which may take any position in the plane. If not stated otherwise our results hold for both disk covers and (homothetic) triangle covers. We focus on the two questions raised before: connectivity and realizability. 2.1 Connectivity It is known to be NP-hard to decide whether a given set of points can be covered by a set of pairwise disjoint open disks, each centered on a point, such that the contact graph of the disks is connected [2]. In contrast to that result we give a simple sweep-line algorithm that covers point seeds by (non-centered) disks such that their contact graph is connected. Proposition 1. Every set Sof npoint seeds has a connected CCG. Such a CCG can be constructed in O(nlog n)time and linear space. Proof. After sorting Sby decreasing ordinate we proceed incrementally from top to bottom. For the first point, we place a cover element (disk or triangle, depending on the case) of fixed size with the seed as its bottommost point. If the k−1 topmost points are already connected, then for the k-th point pwe inflate a cover element Cpwith pas the bottommost point until Cptouches one of the previously placed cover elements. The implementation for disk-CCGs is similar to Fortune’s sweep [6] for constructing the Voronoi diagram of a set of weighted points. For triangle-CCGs we repeatedly determine the size of the new triangle in O(log n)timebyasegmentdragging query [10] and two very simple ray-shooting queries.  In fact, even more can be obtained as the following proposition assures. Proposition 2. Any set Sof npoint seeds has a biconnected CCG. Such a CCG can be constructed in O(n2logn)time using linear space. Proof. We first consider disks as cover elements. Let D1,D2,andD3be three congruent disks that touch each other. They delimit a pseudo-triangular shape R. Choose the three disks such that each disk Dicontains a unique point pi∈S and such that S\{p1,p 2,p 3}⊂R, see Figure 2 (left). In order to cover the remaining points we assume that disks D4,...,D i−1have been placed such that each covers a unique point of Sand touches two previously placed disks, see Figure 2 (middle). Thus the contact graph of D1,...,D i−1is biconnected. Let Rjbe a connected component of R\i−1 j=4 Dithat contains at least one uncovered point. Use Fortune’s sweep [6] to compute the combined Voronoi diagram of the disks incident to Rjand the points in S∩Rj.Thistakes O(nlog n) time and the resulting Voronoi diagram has complexity O(n). The part of the Voronoi diagram in Rjis the locus of the centers of all disks that lie in Rjand touch ∂Rj∪(S∩Rj)inatleasttwopoints,where∂Rjis the boundary of Rj. Now we make a simple but crucial observation: if Dis a disk that (a) lies Cover Contact Graphs 175 D1D2 D3 p1 p3 R p2 D1D2 D3 p1 p3 p4 D4 R7 p5 p6 p2 D1D2 D3 p1 p2 p3 p4 p7 p8 D8 D4D7 R9 p5 p6 Fig. 2. Three steps in the construction of a biconnected disk-CCG in Rj, (b) contains a seed s∈S∩Rjon its boundary, and (c) touches two of the previous disks, then Dis centered at a vertex of the Voronoi diagram. Thus a disk Dfulfilling (a)–(c) can be found in linear time and, by construction, does not contain any point of Sin its interior. (If by any chance all such disks touch more than one point of S, we re-start the whole computation with three slightly wiggled initial disks D1,D2,andD3. Then the probability of this degeneracy becomes 0.) Now set Di=D, and repeat the process until all seeds are covered. This takes O(n2logn) time in total. The case of triangles can be handled analogously. Choosing any reference point in the triangular shape, a structure similar to the medial axis can be computed in O(nlogn) and updated in O(n)timeineachofthen−3 phases.  2.2 Realizability In this section we first give two necessary conditions that a planar graph must fulfill in order to be realizable as a disk-CCG on a given seed set. Then we construct a plane geometric graphs on six vertices that cannot be represented as disk-CCG. Finally we investigate the complexity of deciding realizability. To formulate our necessary conditions for realizability we define a graph on the given seed set S. Our graph is inspired by the sphere-of-influence graph defined by Toussaint [14]. Given a seed set Sand a point p∈Slet the influence area of pbe the closure of the union of all empty open disks D(i.e., D∩S=∅) that are centered at vertices of the Voronoi region of p, see Figure 3. We call the intersection graph of these influence areas the hyperinfluence graph of Sand denote it by HI(S), see Figure 4. Proposition 3. Let Sbe a set of point seeds and let Gbe a graph realizable as a disk-CCG on S.Then (i) Gis a subgraph of HI(S),and (ii) Ghas a plane drawing where each vertex is mapped to a unique point in S and each edge is drawn as a polygonal line with at most two segments (i.e., with at most one bend per edge). 176 N. Atienza et al. p p6 p7 p1 p2 p3 p4 p5 Fig. 3. Influence area of p∈S(shaded) p p6 p7 p1 p2 p3 p4 p5 Fig. 4. The hyperinfluence graph HI(S) Proof. Both facts are straightforward to obtain. (i) is based on the observation that any possible covering disk of pis contained in the influence area of p.Thus, if the covering disks of two seeds are in contact, their influence areas intersect. (ii) is obtained by representing each edge of the CCG by two line segments that connect the seeds with the point of tangency of the covering disks.  While Proposition 3 (ii) is difficult to verify even if all seeds lie on a line [8], Proposition 3 (i) gives us a way to show non-realizability of certain geometric graphs as the one depicted in Figure 5. That graph is connected and thus cannot be realized as a CCG with its vertices as seeds, because the shaded influence areas of p1and p2do not intersect. The graph has eight vertices. On the other hand it is easy to see that any three-vertex graph can be realized on any three-point seed set. Now it is interesting to ask for the least nfor which there is an n-vertex geometric graph Gsuch that the straight-line drawing of Gis plane but Gcannot be realized as CCG. p1p2 Fig. 5. Non-realizable bipartite graph We show that there is a set S={a,b,...,f}of six points in convex position such that their Delaunay triangulation is not representable as a CCG, see the underlying graph in Figure 6. The covering disks Daand Ddof the points aand dmust touch each other in one of two ways. Either the tangent point of the disks lies inside the convex hull of S,orDaand Ddare very large and lie to the left of aand to the right of d, in which case they touch far above or below S,see Figure 6. In the first case there is no disk covering cand touching Da.Inthe second case we can assume that the boundaries of Daand Ddare two almost parallel lines in the vicinity of the six points. The disks Dcand Dfcovering c and fmust both touch Daand Dd.Butifcand fare close enough to aand d then Dcand Dfcannot be disjoint. So we have seen that there are pairs of (quite small) graphs and seed sets such that the graph cannot be realized on theseedsetasdiskCCG.Thuswewould like to decide whether a given graph is realizable as CCG on a given seed set or not. Of course Koebe’s theorem [9] guarantees that for any planar graph G we can find a seed set Ssuch that it is possible to realize Gon S. However, if Cover Contact Graphs 177 f a bc d ef a bc d e DaDd DaDd Dc Df . . .. . . . . .. . . Fig. 6. Non-realizable Delaunay triangulation of six points in convex position the seeds and the vertex–seed correspondence are given, the problem becomes NP-hard. Theorem 1. Given a set Sof points in the plane and a planar graph G=(S, E), it is NP-hard to decide whether Gis realizable as disk-CCG on S. The proof is by reduction from the NP-hard problem Planar3SAT.There are gadgets for each variable and each clause of the given Boolean formula. The gadget of a variable vis such that it allows two combinatorially different ways to represent the given subgraph as disk-CCG. These correspond to the two Boolean values of v. The clause gadget is locally symmetric with respect to 120◦-rotations and designed such that some cover disks must overlap if and only if the corresponding three literals are all false. 3 The Seeds Are Points on a Line In this section, seed sets consist of points on the x-axis. Connectivity follows from some of our realizability results, so we focus on the latter. We consider the following four questions. Note that seeds now correspond to real numbers, so we can use the natural order <in Rto compare them. All covers consist of disks unless stated otherwise (e.g., in Q4). Q1. Given a graph class C(e.g., the class of trees), does it hold that for any seed set Sthere is a graph in Cthat is realizable as CCG or CCG+on S? We show: This is true for (cycles, CCG) and (trees, CCG+). Q2. Given a graph class C, does it hold that for any graph Gin Cthere is a seed set Ssuch that Gcan be realized as CCG or CCG+on S? We show: This is true for the combination (trees, CCG+). Q3. Let Cbe a fixed graph class. Given a graph G∈Cwith a labeling λ:V→ {1,...,n}, is there a sequence s1<...<s nof seeds in R1and a realization of Gthat maps each vertex vto the corresponding seed sλ(v)? We show: There is an O(nlog n) decision algorithm for (trees, CCG+). 178 N. Atienza et al. x ad bc DaDd  (a) Cnis realizable as CCG CCG+ofS tree T(S) r Dr (b) tree T(S) is realizable as CCG+ Fig. 7. Graphs that can be realized on a given one-dimensional n-point seed set S Q4. Let Cbe a fixed graph class. Given a seed set Sand a graph G(S, E)∈C, can Gbe realized on Sas triangle CCG or CCG+? We show: There is an O(nlog n)-time decision algorithm for (trees, CCG+). Note that the above questions require more and more concrete information about the seed set, ranging from no information (Q2) via a fixed order (Q3) to complete information (Q4). We start with question Q1. Proposition 4. Let Sbe a set of npoint seeds on a line, then (i) the n-vertex cycle Cncan be realized as CCG on S,and (ii) there is a tree T(S)that can be realized as CCG+on S. Figures 7a and 7b give some intuition about how our algorithms work; for details see the long version of this paper [3]. In terms of this paper, a coin graph is obtained when seeds are points and cover elements are disks centered at seeds, and thus Koebe’s theorem establishes that it is always possible to choose seeds in the plane such that any given plane graph is realizable as a coin graph on them. We have seen in Proposition 4 that Cnis realizable as a CCG on any seed set on a line. One can ask whether a Koebe-type theorem also holds in this restricted setting. However, Kaufmann and Wiese [7] have shown that there is a plane triangulated 12-vertex graph (see Figure 8) that cannot be drawn with only one bend per edge if vertices are restricted to a line. Now Proposition 3 (ii) implies that that graph is not realizable as CCG if seeds lie on a line. On the positive side, we can show that a Koebe-type theorem holds for the combination (trees, CCG+). This is an answer to Q2 and in a way dual to Proposition 4 (ii). See Figure 9 for a sketch of our recursive construction. Proposition 5. For any tree Tthere is a seed set S(T)⊂R1such that Tis realizable as CCG+on S(T). Cover Contact Graphs 179 vr1 r2 r3 D0 D1 D2 D3 0 1 2 3 R2R110 Fig. 8. Kaufmann–Wiese graph [8] Fig. 9. Constructing a seed set S(T) In Proposition 5 above, we had complete freedom to choose the seeds. Now we turn to question Q3, where we are not just given a tree, but also an order of its vertices that must be respected by the corresponding seeds. Kaufmann and Wiese [7] have investigated a related problem. They showed that it is NP-complete to decide whether the vertices of a given (planar) graph can be put into one-to-one correspondence with a given set of points on a line such that there is a plane drawing of the graph with at most one bend per edge. We call such a drawing a 1d-1BD. If additionally all bends lie on one side of the line, we call the drawing a1d-1BD +. Note that the hardness result of Kaufmann and Wiese does not yield the hardness of the one-dimensional CCG realizability problem, since not every graph that can be one-bend embedded on a set of points on a line is realizable as CCG, let alone as CCG+. Our next result explores the gap between Kaufmann and Wiese’s one-dimensional embeddability problem and the situation in Proposition 5. More formally, given an n-vertex tree Tand a (bijective) labeling λ:V→ {1,...,n}of its vertices, we say that Tis λ-realizable (as CCG, CCG+,1d- 1BD, 1d-1BD+) if there is a sequence s1< ... < s nof seeds in R1and a realization of T(as CCG, CCG+, 1d-1BD, 1d-1BD+)thatmapseachvertexv to the corresponding seed sλ(v). In order to obtain a characterization of trees that are λ-realizable as CCG+,we need the following definition. Given a graph G=(V,E) with vertex labeling λ, aforbidden pair is a pair of edges {a, b},{c, d}such that λ(a)<λ(c)< λ(b)<λ(d). Note that it is impossible to embed the edges of a forbidden pair simultaneously above the x-axis. Theorem 2. For a λ-labeled tree Tthe following statements are equivalent: (i) Tis λ-realizable as a CCG+. (ii) Tis λ-realizable as a 1d-1BD+. (iii) Tdoes not contain any forbidden pair. Given the tree, statement (iii) can be checked in O(nlog n) time using an interval tree, therefore the following corollary is straightforward.