Carregant...
Carregant...

Vés al contingut (premeu Retorn)

A polynomial bound for untangling geometric planar graphs

Autor
Bose, P.; Dujmovic, V.; Hurtado, F.; Langerman, S.; Morin, P.; Wood, D.
Tipus d'activitat
Article en revista
Revista
Discrete and computational geometry
Data de publicació
2009-12
Volum
42
Número
4
Pàgina inicial
570
Pàgina final
585
DOI
https://doi.org/10.1007/s00454-008-9125-3 Obrir en finestra nova
Repositori
http://hdl.handle.net/2117/9583 Obrir en finestra nova
URL
http://arxiv.org/PS_cache/arxiv/pdf/0710/0710.1641v2.pdf Obrir en finestra nova
Resum
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^\in{}$ vertices fixed. We answer this question in the affirmative with ∊ = 1/4. The previous best known bound was Ω$(\sqrt{log\,n/log\,log\,n})$. We also consider untangling geometric trees. It is known that every n-verte...
Citació
Bose, P. [et al.]. A polynomial bound for untangling geometric planar graphs. "Discrete and computational geometry", Desembre 2009, vol. 42, núm. 4, p. 570-585.
Grup de recerca
DCG - Discrete and Combinatorial Geometry

Participants

  • Bose, Prosenjit  (autor)
  • Dujmovic, Vida  (autor)
  • Hurtado Diaz, Fernando Alfredo  (autor)
  • Langerman, Stefan  (autor)
  • Morin, Pat  (autor)
  • Wood, David R.  (autor)

Arxius