Abstract
Untangling is a process in which some vertices in a drawing of a planar graph are moved to obtain a straight-line plane drawing. The aim is to move as few vertices as possible. We present an algorithm that untangles the cycle graph C n while keeping Ω(n 2/3) vertices fixed.
For any connected graph G, we also present an upper bound on the number of fixed vertices in the worst case. The bound is a function of the number of vertices, maximum degree, and diameter of G. One consequence is that every 3-connected planar graph has a drawing δ such that at most O((nlog n)2/3) vertices are fixed in every untangling of δ.
Article PDF
Similar content being viewed by others
References
Barnette, D.: Trees in polyhedral graphs. Can. J. Math. 18, 731–736 (1966)
Bose, P., Dujmović, V., Hurtado, F., Langerman, S., Morin, P., Wood, D.: A polynomial bound for untangling geometric planar graphs. Discrete Comput. Geom. (2008). doi:10.1007/s00454-008-9125-3
Erdős, P., Szekeres, G.: A combinatorial problem in geometry. Compos. Math. 2, 463–470 (1935)
Fáry, I.: On straight line representation of planar graphs. Acta Univ. Szeged, Acta Sci. Math. 11, 229–233 (1948)
Goaoc, X., Kratochvíl, J., Okamoto, Y., Shin, C.-S., Spillner, A., Wolff, A.: Untangling a planar graph. Discrete Comput. Geom. (2009) doi:10.1007/s00454-008-9130-6
Kang, M., Pikhurko, O., Ravsky, A., Schacht, M., Verbitsky, O.: Obfuscated drawings of planar graphs. 0803.0858
Pach, J., Tardos, G.: Untangling a polygon. Discrete Comput. Geom. 28(4), 585–592 (2002)
Ravsky, A., Verbitsky, O.: On collinear sets in straight line drawings. 0806.0253
Stein, S.K.: Convex maps. Proc. Am. Math. Soc. 2, 464–466 (1951)
Verbitsky, O.: On the obfuscation complexity of planar graphs. Theor. Comput. Sci. 396(1–3), 294–300 (2008)
Wagner, K.: Bemerkungen zum Vierfarbenproblem. Jahresber. Deutsch. Math. Verein. 46, 26–32 (1936)
Author information
Authors and Affiliations
Corresponding author
Additional information
Supported by project MSM0021620838 of the Czech Ministry of Education.
Rights and permissions
About this article
Cite this article
Cibulka, J. Untangling Polygons and Graphs. Discrete Comput Geom 43, 402–411 (2010). https://doi.org/10.1007/s00454-009-9150-x
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-009-9150-x