Movatterモバイル変換

[0]ホーム
URL:

Skip to main content
Springer Nature Link
Log in

A Polynomial Bound for Untangling Geometric Planar Graphs

  • Published:
Discrete & Computational Geometry Aims and scope Submit manuscript

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 everyn-vertex geometric planar graph can be untangled while keeping at leastnε 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 everyn-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 ann-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

Explore related subjects

Discover the latest articles and news from researchers in related subjects, suggested using machine learning.
Use our pre-submission checklist

Avoid common mistakes on your manuscript.

References

  1. Abellanas, M., Hurtado, F., Ramos, P.: Tolerancia de arreglos de segmentos. In: Proc. VI Encuentros de Geometría Computacional, pp. 77–84 (1995)

  2. Cibulka, J.: Untangling polygons and graphs. In: Topological and Geometric Graph Theory. Electronic Notes in Discrete Mathematics, vol. 31, pp. 207–211 (2008)

  3. de Fraysseix, H., Pach, J., Pollac, R.: How to draw a planar graph on a grid. Combinatorica10(1), 41–51 (1990)

    Article MATH MathSciNet  Google Scholar 

  4. Dilworth, R.P.: A decomposition theorem for partially ordered sets. Ann. Math.51(2), 161–166 (1950)

    Article MathSciNet  Google Scholar 

  5. Erdős, P., Szekeres, G.: A combinatorial problem in geometry. Compos. Math.2, 464–470 (1935)

    Google Scholar 

  6. Fáry, I.: On straight line representation of planar graphs. Acta Univ. Szeged. Sect. Sci. Math.11, 229–233 (1948)

    MathSciNet  Google Scholar 

  7. 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 inhttp://arxiv.org/abs/0706.1002

    Google Scholar 

  8. Hong, S.-H., Nagamochi, H.: Convex drawings of graphs with non-convex boundary constraints. Discrete Appl. Math.156(12), 2368–2380 (2008)

    Article MATH MathSciNet  Google Scholar 

  9. Kang, M., Pikhurko, O., Ravsky, A., Schacht, M., Verbitsky, O.: Obfuscated drawings of planar graphs (2008).http://arxiv.org/abs/0803.0858

  10. 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

  11. Pach, J., Tardos, G.: Untangling a polygon. Discrete Comput. Geom.28(4), 585–592 (2002)

    MATH MathSciNet  Google Scholar 

  12. Ramos, P.: Tolerancia de estructuras geométricas y combinatorias. Ph.D. thesis, Universidad Politécnica de Madrid, Madrid, Spain (1995)

  13. Ravsky, A., Verbitsky, O.: On collinear sets in straight line drawings (2008).http://arxiv.org/abs/0806.0253

  14. 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 inhttp://arxiv.org/abs/0709.0170

    Google Scholar 

  15. Verbitsky, O.: On the obfuscation complexity of planar graphs. Theor. Comput. Sci.396(1–3), 294–300 (2008)

    Article MATH MathSciNet  Google Scholar 

  16. Wagner, K.: Über eine Eigenschaft der ebene Komplexe. Math. Ann.114, 570–590 (1937)

    Article MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Computer Science, Carleton University, Ottawa, Canada

    Prosenjit Bose & Pat Morin

  2. Department of Mathematics and Statistics, McGill University, Montreal, Canada

    Vida Dujmović

  3. Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya, Barcelona, Spain

    Ferran Hurtado

  4. FNRS, Département d’Informatique, Université Libre de Bruxelles, Brussels, Belgium

    Stefan Langerman

  5. Department of Mathematics and Statistics, The University of Melbourne, Melbourne, Australia

    David R. Wood

Authors
  1. Prosenjit Bose

    You can also search for this author inPubMed Google Scholar

  2. Vida Dujmović

    You can also search for this author inPubMed Google Scholar

  3. Ferran Hurtado

    You can also search for this author inPubMed Google Scholar

  4. Stefan Langerman

    You can also search for this author inPubMed Google Scholar

  5. Pat Morin

    You can also search for this author inPubMed Google Scholar

  6. David R. Wood

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence toProsenjit Bose.

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 Geom42, 570–585 (2009). https://doi.org/10.1007/s00454-008-9125-3

Download citation

Keywords

Profiles

  1. Prosenjit BoseView author profile
Use our pre-submission checklist

Avoid common mistakes on your manuscript.

Advertisement

[8]ページ先頭
©2009-2025 Movatter.jp