zbMATH — the first resource for mathematics

Simultaneously flippable edges in triangulations. (English) Zbl 1374.05073
Márquez, Alberto (ed.) et al., Computational geometry. XIV Spanish meeting on computational geometry, EGC 2011, dedicated to Ferran Hurtado on the occasion of his 60th birthday, Alcalá de Henares, Spain, June 27–30, 2011. Revised selected papers. Berlin: Springer (ISBN 978-3-642-34190-8/pbk). Lecture Notes in Computer Science 7579, 138-145 (2012).
Summary: Given a straight-line triangulation $$T$$, an edge $$e$$ in $$T$$ is flippable if $$e$$ is adjacent to two triangles that form a convex quadrilateral. A set of edges $$E$$ in $$T$$ is simultaneously flippable if each edge is flippable and no two edges are adjacent to a common triangle. Intuitively, an edge is flippable if it may be replaced with the other diagonal of its quadrilateral without creating edge-edge intersections, and a set of edges is simultaneously flippable if they may be all be flipped without interferring with each other. We show that every straight-line triangulation on $$n$$ vertices contains at least $$(n-4)/5$$ simultaneously flippable edges. This bound is the best possible, and resolves an open problem by J. Galtier et al. [Int. J. Comput. Geom. Appl. 13, No. 2, 113–133 (2003; Zbl 1058.52005)].
For the entire collection see [Zbl 1253.68016].

MSC:
 05C10 Planar graphs; geometric and topological aspects of graph theory
Full Text:
References:
 [1] Bose, P., Hurtado, F.: Flips in planar graphs. Computational Geometry: Theory and Applications 42, 60–80 (2009) · Zbl 1146.05016 · doi:10.1016/j.comgeo.2008.04.001 [2] Dumitrescu, A., Schulz, A., Sheffer, A., Tóth, C.D.: Bounds on the maximum multiplicity of some common geometric graphs. In: 28th International Symposium on Theoretical Aspects of Computer Science, pp. 637–648. Dagstuhl Publishing, Germany (2011) · Zbl 1230.68206 [3] Galtier, J., Hurtado, F., Noy, M., Pérennes, S., Urrutia, J.: Simultaneous edge flipping in triangulations. International Journal of Computational Geometry and Applications 13, 113–133 (2003) · Zbl 1058.52005 · doi:10.1142/S0218195903001098 [4] Hoffmann, M., Sharir, M., Sheffer, A., Tóth, C.D., Welzl, E.: Counting Plane Graphs: Flippability and Its Applications. In: Dehne, F., Iacono, J., Sack, J.-R. (eds.) WADS 2011. LNCS, vol. 6844, pp. 524–535. Springer, Heidelberg (2011) · Zbl 1342.68257 · doi:10.1007/978-3-642-22300-6_44 [5] Hurtado, F., Noy, M., Urrutia, J.: Flipping edges in triangulations. Discrete and Compututational Geometry 22, 333–346 (1999) · Zbl 0939.68135 · doi:10.1007/PL00009464 [6] Mucha, M., Sankowski, P.: Maximum matchings in planar graphs via Gaussian elimination. Algorithmica 45, 3–20 (2006) · Zbl 1117.68056 · doi:10.1007/s00453-005-1187-5 [7] Micali, S., Vazirani, V.V.: An $$O(\sqrt{|V|}\cdot|E|)$$ algorithm for finding maximum matching in general graphs. In: 21st IEEE Symposium on Foundations of Computer Science, pp. 17–27. IEEE Press, New York (1980) [8] Urrutia, J.: Flipping edges in triangulations of point sets, polygons and maximal planar graphs. Invited talk, 1st Japanese Conference on Discrete and Computational Geometry, JCDCG 1997 (1997), http://www.matem.unam.mx/ urrutia/online_papers/TrianSurv.pdf
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.