Back to Search
Start Over
A polynomial bound for untangling geometric planar graphs
- Source :
- UPCommons. Portal del coneixement obert de la UPC, Universitat Politècnica de Catalunya (UPC), Recercat. Dipósit de la Recerca de Catalunya, instname
- Publication Year :
- 2009
-
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., 2002] asked if every n-vertex geometric planar graph can be untangled while keeping at least n^\epsilon vertices fixed. We answer this question in the affirmative with \epsilon=1/4. The previous best known bound was \Omega((\log n / \log\log n)^{1/2}). We also consider untangling geometric trees. It is known that every n-vertex geometric tree can be untangled while keeping at least (n/3)^{1/2} vertices fixed, while the best upper bound was O(n\log n)^{2/3}. We answer a question of Spillner and Wolff [arXiv:0709.0170 2007] 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(n^{1/2}-1) vertices fixed. Moreover, we improve the lower bound to (n/2)^{1/2}.<br />Comment: 14 pages, 7 figures
- Subjects :
- Computational Geometry (cs.CG)
FOS: Computer and information sciences
Discrete Mathematics (cs.DM)
Planar straight-line graph
0102 computer and information sciences
Computer Science::Computational Geometry
Geometria discreta
Matemàtiques i estadística::Geometria::Geometria convexa i discreta [Àrees temàtiques de la UPC]
Upper and lower bounds
Omega
01 natural sciences
Polynomials
Theoretical Computer Science
Combinatorics
Tree (descriptive set theory)
symbols.namesake
Spatial network
Pathwidth
Computer Science::Discrete Mathematics
Outerplanar graph
FOS: Mathematics
Discrete Mathematics and Combinatorics
Mathematics - Combinatorics
0101 mathematics
Mathematics
Polyhedral graph
Polynomial (hyperelastic model)
Discrete mathematics
Book embedding
Grafs, Teoria de
Applied Mathematics
010102 general mathematics
Discrete geometry
Binary logarithm
1-planar graph
Planar graph
Graph theory
Crossings
Computational Theory and Mathematics
010201 computation theory & mathematics
symbols
Computer Science - Computational Geometry
Polinomis
Combinatorics (math.CO)
Geometry and Topology
Tutte polynomial
Computer Science - Discrete Mathematics
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Journal :
- UPCommons. Portal del coneixement obert de la UPC, Universitat Politècnica de Catalunya (UPC), Recercat. Dipósit de la Recerca de Catalunya, instname
- Accession number :
- edsair.doi.dedup.....e17ccf17ffa538d63b33b8f9a1c128f8
- Full Text :
- https://doi.org/10.1007/s00454-008-9125-3