Abstract
To untangle a geometric graph means to move some of the vertices so that the resulting geometric graph has no crossings. Pach and Tardos (Discrete Comput. Geom. 28(4): 585–592, 2002) asked if every n-vertex geometric planar graph can be untangled while keeping at least n ε vertices fixed. We answer this question in the affirmative with ε=1/4. The previous best known bound was \(\Omega(\sqrt{\log n/\log\log n})\) . We also consider untangling geometric trees. It is known that every n-vertex geometric tree can be untangled while keeping at least \(\Omega(\sqrt{n})\) vertices fixed, while the best upper bound was \(\mathcal{O}((n\log n)^{2/3})\) . We answer a question of Spillner and Wolff (http://arxiv.org/abs/0709.0170) by closing this gap for untangling trees. In particular, we show that for infinitely many values of n, there is an n-vertex geometric tree that cannot be untangled while keeping more than \(3(\sqrt{n}-1)\) vertices fixed.
Article PDF
Similar content being viewed by others
References
Abellanas, M., Hurtado, F., Ramos, P.: Tolerancia de arreglos de segmentos. In: Proc. VI Encuentros de Geometría Computacional, pp. 77–84 (1995)
Cibulka, J.: Untangling polygons and graphs. In: Topological and Geometric Graph Theory. Electronic Notes in Discrete Mathematics, vol. 31, pp. 207–211 (2008)
de Fraysseix, H., Pach, J., Pollac, R.: How to draw a planar graph on a grid. Combinatorica 10(1), 41–51 (1990)
Dilworth, R.P.: A decomposition theorem for partially ordered sets. Ann. Math. 51(2), 161–166 (1950)
Erdős, P., Szekeres, G.: A combinatorial problem in geometry. Compos. Math. 2, 464–470 (1935)
Fáry, I.: On straight line representation of planar graphs. Acta Univ. Szeged. Sect. Sci. Math. 11, 229–233 (1948)
Goaoc, X., Kratochvil, J., Okamoto, Y., Shin, C.-S., Wolff, A.: Moving vertices to make drawings plane. In: Proc. 15th International Symp. on Graph Drawing (GD’07). Lecture Notes in Computer Science, vol. 4875, pp. 101–112. Springer, Berlin (2008). Also in http://arxiv.org/abs/0706.1002
Hong, S.-H., Nagamochi, H.: Convex drawings of graphs with non-convex boundary constraints. Discrete Appl. Math. 156(12), 2368–2380 (2008)
Kang, M., Pikhurko, O., Ravsky, A., Schacht, M., Verbitsky, O.: Obfuscated drawings of planar graphs (2008). http://arxiv.org/abs/0803.0858
Kang, M., Schacht, M., Verbitsky, O.: How much work does it take to straighten a plane graph out? (2007). http://arxiv.org/abs/0707.3373
Pach, J., Tardos, G.: Untangling a polygon. Discrete Comput. Geom. 28(4), 585–592 (2002)
Ramos, P.: Tolerancia de estructuras geométricas y combinatorias. Ph.D. thesis, Universidad Politécnica de Madrid, Madrid, Spain (1995)
Ravsky, A., Verbitsky, O.: On collinear sets in straight line drawings (2008). http://arxiv.org/abs/0806.0253
Spillner, A., Wolff, A.: Untangling a planar graph. In: Proc. 34th Internat. Conf. on Current Trends in Theory and Practice of Computer Science (SOFSEM’08). Lecture Notes in Computer Science, vol. 4910, pp. 473–484. Springer, Berlin (2008). Also in http://arxiv.org/abs/0709.0170
Verbitsky, O.: On the obfuscation complexity of planar graphs. Theor. Comput. Sci. 396(1–3), 294–300 (2008)
Wagner, K.: Über eine Eigenschaft der ebene Komplexe. Math. Ann. 114, 570–590 (1937)
Author information
Authors and Affiliations
Corresponding author
Additional information
Research of P. Bose and P. Morin was partially supported by NSERC.
Research of V. Dujmović was partially supported by CRM and NSERC.
Research of F. Hurtado was supported by projects MEC MTM2006-01267 and DURSI 2005SGR00692.
Research of D.R. Wood was supported by a QEII Research Fellowship. Research initiated at the Universitat Politècnica de Catalunya, where supported by the Marie Curie Fellowship MEIF-CT-2006-023865, and by projects MEC MTM2006-01267 and DURSI 2005SGR00692.
Rights and permissions
About this article
Cite this article
Bose, P., Dujmović, V., Hurtado, F. et al. A Polynomial Bound for Untangling Geometric Planar Graphs. Discrete Comput Geom 42, 570–585 (2009). https://doi.org/10.1007/s00454-008-9125-3
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-008-9125-3