Flips in combinatorial pointed pseudo-triangulations with face degree at most four

XV Spanish Meeting on Computational Geometry, June 26-28, 2013 Flips in combinatorial pointed pseudo-triangulations with face degree at most four (extended abstract) Oswin Aichholzer ∗ 1 , Thomas Hackl ∗ 1 , David Orden † 2 , Alexander Pilz ∗ 1 , Maria Saumell ‡ 3 , and Birgit Vogtenhuber ∗ 1 1 Institute for Software Technology, Graz University of Technology, Austria. 2 Departamento de Física y Matemáticas, Universidad de Alcalá, Spain. 3 Département d'Informatique, Université Libre de Bruxelles, Belgium. Abstract In this paper we consider the ip operation for combinatorial pointed pseudo-triangulations where faces have size 3 or 4, so-called combinatorial 4-PPTs . We show that every combinatorial 4-PPT is stretchable to a geometric pseudo-triangulation, which in general is not the case if faces may have size larger than 4. Moreover, we prove that the ip graph of combinatorial 4-PPTs with triangular outer face is connected and has diameter O(n2) . 1 Introduction Given a graph of a certain class, a ip is the operation of removing one edge and inserting a dierent one such that the resulting graph is again of the same class. For the class of maximal planar (simple) graphs, any combinatorial embedding (clockwise order of edges around each vertex) has only faces of size 3 and hence is called a combinatorial triangulation . Flips in combinatorial triangulations remove the common edge of two triangular faces and replace it by the edge between the two vertices not shared by the faces, provided that these two vertices where not already joined by an edge. Combinatorial triangulations have a geometric counterpart in triangulations of point sets in the plane, which are maximal plane ∗ Email: [oaich|thackl|apilz|bvogt]@ist.tugraz.at. Research of OA and BV partially supported by the ESF EUROCORES programme EuroGIGA  CRP `ComPoSe', Austrian Science Fund (FWF): I648-N18. Research of TH supported by the Austrian Science Fund (FWF): P23629-N18 `Combinatorial Problems on Geometric Graphs'. AP is a recipient of a DOC- fellowship of the Austrian Academy of Sciences. † Email: da[email protected]. Research partially supported by MICINN Project MTM2011-22792, ESF EUROCORES programme EuroGIGA - ComPoSe IP04 - MICINN Project EUI-EURC-2011-4306 and Junta de Castilla y León Project VA172A12-2. ‡ Email: [email protected]. Research supported by ESF EuroGIGA project ComPoSe as F.R.S.-FNRS - EUROGIGA NR 13604 and by ESF EuroGIGA project GraDR as GAR GIG/11/E023. geometric (straight-line) graphs with predened vertex positions. In this geometric setting there is also a ip operation, for which a dierent restriction applies: An edge can be ipped if and only if the two adjacent triangles form a convex quadrilateral (otherwise the new edge would create a crossing). Flips in (combinatorial) triangulations have been thoroughly studied. See [4] for a survey. A prominent question about ips is to study the ip graph . This is an abstract graph whose vertices are the members of the same graph class having the same number of vertices, and in which two graphs are neighbors if and only if one can be transformed into the other by a single ip. For both, combinatorial triangulations and triangulations (with xed vertex positions), the ip graph is connected. However, the dierent settings imply linear and quadratic diameter, respectively (see [4] for references). Triangulations have a natural generalization in pseudo-triangulations. They have become a popular structure in Computational Geometry within the last two decades, with applications in, e.g., rigidity theory and motion planning. See [7] for a survey. A pseudo-triangle is a simple polygon in the plane with exactly three convex vertices (i.e., vertices whose interior angle is smaller than π ). A pseudotriangulation T of a nite point set S in the plane is a partition of the convex hull of S into pseudotriangles such that the union of the vertices of the pseudo-triangles is exactly S . Triangulations are a particular type of pseudo-triangulations, actually the ones with the maximum number of edges. Those with the minimum number of edges are the so-called pointed pseudo-triangulations , in which every vertex is pointed , i.e., incident to a reex angle (an angle larger than π ). Flips can also be dened for the class of pseudotriangulations of point sets in the plane. The ip graph for general pseudo-triangulations is known to be connected, as well as the subgraph induced by pointed pseudo-triangulations. The currently best known bound on the diameter is O(nlog n) for both 131 Flips in combinatorial pointed pseudo-triangulations with face degree at most four (extended abstract) ip graphs [2, 3]. In a pseudo-triangulation, the pseudo-triangles can have linear size. Hence, in contrast to triangulations, the ip operation can no longer be computed in constant time. This fact led to the consideration of pseudo-triangulations in which the size of the pseudotriangles is bounded by a constant. Kettner et al. [5] showed that every point set admits a pointed pseudotriangulation with face degree at most four (except, maybe, for the outer face). We call such a pseudotriangulation a 4-PPT . On the one hand, 4-PPTs behave nicely for problems which are hard for general pseudo-triangulations. For instance, they are always properly 3-colorable, while 3-colorability is NP-complete to decide for general pseudo-triangulations [1]. On the other hand, known properties of general pseudo-triangulations remain open for 4-PPTs. For instance, it is not known whether the ip graph of 4-PPTs is connected, even for the basic case of a triangular convex hull. The aim of this paper is to make a step towards answering this last question, by considering the combinatorial counterpart of 4-PPTs. A combinatorial pseudo-triangulation [6] is a topological embedding of a planar simple graph together with an assignment of labels reex/convex to its angles such that (1) every interior face has exactly three angles labeled convex, (2) all the angles of the outer face are labeled reex, and (3) no vertex is incident to more than one reex angle. Note that this labeling fullls the same properties as actual reex/convex angles in a (geometric) pseudo-triangulation. This analogy with the geometric case goes on by calling pointed vertices in a combinatorial pseudo-triangulation those which, indeed, are incident to one angle labeled reex. Then, combinatorial pointed pseudo-triangulations are those in which every vertex is pointed. Combinatorial pointed pseudo-triangulations with face degree at most four (except, maybe, for the outer face), will be called combinatorial 4-PPTs . 2 Properties Lemma 1 Let G be a combinatorial 4-PPT and H be a subgraph of G with |V(H)| ≥ 3 . Then H has at least 3 vertices whose reex angle is contained in the outer face of H (corners of rst type in [6]). Corollary 2 In any combinatorial 4-PPT of the interior of a simple cycle with b vertices, of which c have the reex angle inside the cycle, the number t of triangular faces is given by t=b−2c−2 . A combinatorial pseudo-triangulation has the generalized Laman property if every subset of x non-poin- ted vertices and y pointed vertices, where x+y≥2 , induces a subgraph with at most 3x+ 2y−3 edges. Both this property and the number of reex angles from Lemma 1 are related to the stretchability of a combinatorial pseudo-triangulation into a geometric one. A face of a combinatorial pseudo-triangulation is called degenerate if it contains edges which appear twice on the boundary of this face. Proposition 3 [6, Corollary 2] The following properties are equivalent for a combinatorial pseudotriangulation G : (1) G can be stretched to become a pseudo-triangulation. (2) G has the generalized Laman property. (3) G has no degenerate faces and every subgraph of G with at least three vertices has at least three corners of rst type. Since, by denition, combinatorial 4-PPTs have no degenerate faces, we can use Proposition 3 to conclude the following. Theorem 4 Every combinatorial 4-PPT can be stretched to become a 4-PPT with the given assignment of angles. Furthermore, combinatorial 4-PPTs have the generalized Laman property. Note that there exist non-stretchable combinatorial pointed pseudo-triangulations with faces of size at most 5. See Figure 1. There and in the forthcoming gures, arcs denote angles labeled as reex. Figure 1: A non-stretchable combinatorial pointed pseudo-triangulation [6]. 3 Flips In the following we focus on combinatorial 4-PPTs with a xed triangular outer face. For such a combinatorial 4-PPT, Corollary 2 implies that there is only one interior triangular face. Before dening ips between combinatorial 4-PPTs, we make some observations about their geometric counterpart. Geometric 4-PPTs with triangular convex hull also have only one interior triangle. Furthermore, every edge of the triangle (except for those being part of the convex hull) is ippable [7]. Observe that the removal of the edge e to be ipped merges the triangle and the 4-face adjacent at e into a 5-face, which might be degenerate if the triangle and the 4-face share two edges. See Figure 2. Note that this is the only case in which the triangle and the 4-face can share three vertices, as there are no multiple edges in geometric graphs. 132 XV Spanish Meeting on Computational Geometry, June 26-28, 2013 Figure 2: Geometric ip of an edge of a triangle. In the lower case, removal of the ipped edge gives a degenerate 5-face. Similar to the geometric case, we consider ips of an edge e of the (unique) interior triangular face T in a combinatorial 4-PPT (with triangular outer face): Consider the 4-face F sharing e with T . A ip of e consists in replacing e by another edge e0 such that (1) e0 splits (T∪F)\e into a triangular face T0 and a 4-face F0 and (2) the result is a combinatorial 4-PPT. In particular, and in contrast to the geometric case, in the combinatorial setting we have to explicitly avoid multiple edges and thus to ensure that the edge e0 we insert is not already contained in the combinatorial 4-PPT (as an edge outside T∪F ). The following lemma shows that every interior edge of the interior triangular face can be ipped. Lemma 5 In a combinatorial 4-PPT, every edge e of an interior triangular face that is not an edge of the outer face is ippable. Furthermore: (1) If the removal of e results in a degenerate 5-face, then there is a unique valid ip for e . (2) If removing e results in a non-degenerate 5-face, then there are at least two valid ips for e . Observe that, given a combinatorial ip between two combinatorial 4-PPTs, by Theorem 4 we know that both of them can be stretched into geometric 4- PPTs with straight edges. However, it might not be possible to use the same geometric embedding for the vertices in both of them. 4 Flip graph connectivity Lemma 6 For a given combinatorial 4-PPT with triangular outer face and for any edge b of this outer face, there is a sequence of ips resulting in a combinatorial 4-PPT whose interior triangular face is incident to b . Once the interior triangular face is incident to an edge b of the outer face, the next step will be ipping away interior edges incident to one endpoint of b . Lemma 7 Given a combinatorial 4-PPT with triangular outer face, in which the interior triangular face T is incident to the edge b of the outer face, there is a sequence of ips resulting in a combinatorial 4- PPT in which the endpoint v of b=uv has no interior incident edges. Proof. We describe a ip sequence that ips all inner edges incident to v . This ip sequence can be partitioned into two phases and some cases. Let the vertices neighbored to the vertex v be ordered radially around v , starting with u . In each case, let the vertices in that order be u=w0, . . . , wk . Phase 1: During this phase, the inner triangular face T has uv as a side, i.e., T=vuw1 . We distinguish three dierent cases: Case 1: vw1 is the only inner edge incident to v , i.e., k= 2 . If T is incident to only one 4-face F (i.e., T∪F is degenerate), we can ip the edge vw1 and are done. Otherwise, let the 4-face F incident to vw1 be vw1sw2 . See Figure 3. The reex angle inside F is either at s or w1 . If it is at s , we ip vw1 to w0s , obtaining the 4-face vw0sw2 . Otherwise, the reex angle is at w1 and we ip vw1 to w1w2 , obtaining the 4-face vw0w1w2 . Either way, the degree of v is 2 and we are done. v w1 s v w1 w2w0 u=w0 v w1 v s u=w0w2 w2 w2 w0 s w1 s Figure 3: Phase 1, Case 1: Only one interior edge is incident to v . Case 2: at least two inner edges are incident to v and there does not exist an edge w0w2 . See Figure 4. Since the reex angle of v is at the outer face we can replace the edge vw1 by w0w2 . This reduces the degree of v by one. The inner triangular face is again adjacent to w0v , and we remain in Phase 1. w1 w2 v v u=w0w0 w2 w1 Figure 4: Phase 1, Case 2: Several interior edges are incident to v and w0w2 does not exist. 133 Flips in combinatorial pointed pseudo-triangulations with face degree at most four (extended abstract) Case 3: at least two inner edges are incident to v and there exists an edge w0w2 . See Figure 5. If the two inner edges of T are incident to a single 4-face, we have a degenerate case; we ip the edge w0w1 to w1w2 , making vw1w2 the inner triangular face. Otherwise, let the 4-face F incident to vw1 be vw1sw2 ; we ip vw1 to vs (this is possible since if vs already existed, it would have to cross the cycle uw2sw1 ). Either way, the ip does not reduce the degree of v , but the inner triangular face is now inside the 3-cycle vw0w2 . We switch to Phase 2. w1 w2w2 w2 w1 w2 s s u=w0 u=w0 w0 w0 v v v v w1 w1 Figure 5: Phase 1, Case 3: The possible transitions to Phase 2. Phase 2: During this phase, the inner triangular face is vw1w2 , and w1 stays xed for the whole phase. Further, we know that w1 was enclosed by a 3-cycle (at the transition to this phase), which implies that there are no edges from w1 to wi for any i≥2 . We decrease the degree of v in the following manner. Case 1: there is a 4-face F incident to vw2 . There cannot be an edge w1w3 since w1 was enclosed by a 3-cycle. Further, the reex angle of F is not at v . Hence, we can ip vw2 to w1w3 , which reduces the degree of v and we remain in Phase 2, with vw1w3 being the new inner triangular face. Case 2: there is no 4-face incident to vw2 , i.e., k= 2 . This case is symmetric to Case 1 of Phase 1. The edge vw1 is ipped in one of the two described ways, reducing the degree of v to 2 and thus ending the process.  Theorem 8 The graph of ips in combinatorial 4- PPTs with n vertices and triangular outer face is connected and has diameter O(n2) . Proof. Given such a combinatorial 4-PPT, follow the steps in Lemmas 6 and 7, then use induction for the combinatorial 4-PPT obtained by removing v . This leads to the unique canonical combinatorial 4-PPT with triangular outer face, where two of the vertices in the outer face are adjacent to all other vertices, while the third one has degree 2. See Figure 6. Figure 6: A canonical combinatorial 4-PPT. Furthermore, the number of ips needed in Lemmas 6 and 7 is at most linear in the number of vertices of the combinatorial 4-PPT.  The presented basic case of combinatorial 4-PPTs with triangular outer face is extendible to an arbitrarily sized outer face, to labeled vertices, and also to the general case of combinatorial 4-PPTs with an arbitrarily sized outer face on labeled vertices. Elaborating on these extensions would go beyond the scope of this extended abstract, though. Details (and omitted proofs) can be found in a forthcoming full version. Acknowledgments. This work was initiated during the 9 th European Research Week on Geometric Graphs and Pseudo-Triangulations, held May 1418, 2012 in Alcalá de Henares, Spain. We thank Vincent Pilaud, Pedro Ramos, and André Schulz for helpful comments. References [1] O. Aichholzer, F. Aurenhammer, T. Hackl, C. Huemer, A. Pilz, and B. Vogtenhuber. 3- colorability of pseudo-triangulations. In EuroCG 2010 , pages 2124, 2010. [2] O. Aichholzer, F. Aurenhammer, H. Krasser, and P. Braÿ. Pseudotriangulations from surfaces and a novel type of edge ip. SIAM J. Comput. , 32(6):16211653, 2003. [3] S. Bereg. Transforming pseudo-triangulations. Inf. Process. Lett. , 90(3):141145, 2004. [4] P. Bose and F. Hurtado. Flips in planar graphs. Comput. Geom. , 42(1):6080, 2009. [5] L. Kettner, D. Kirkpatrick, A. Mantler, J. Snoeyink, B. Speckmann, and F. Takeuchi. Tight degree bounds for pseudo-triangulations of points. Comput. Geom. , 25(12):312, 2003. [6] D. Orden, F. Santos, B. Servatius, and H. Servatius. Combinatorial pseudo-triangulations. Discrete Math. , 307(35):554566, 2007. [7] G. Rote, F. Santos, and I. Streinu. Pseudotriangulations  a survey . Contemp. Math. AMS, 2008. 134