Paper Info
Title
Untangling a Planar Graph.
Abstract
In John Tantalo's on-line game Planarity the player is given a non-plane straight-line drawing of a planar graph. The aim is to make the drawing plane as quickly as possible by moving vertices. Pach and Tardos have posed a related problem: can any straight-line drawing of any planar graph with n vertices be made plane by vertex moves while keeping (n") vertices fixed for some absolute constant ε > 0? It is known that three vertices can always be kept (if n � 5). We still do not solve the problem of Pach and Tardos, but we report some progress. We prove that the number of vertices that can be kept actually grows with the size of the graph. More specifically, we give a lower bound of ( p log n/log log n) on this number. By the same technique we show that in the case of outerplanar graphs we can keep a lot more, namely ( p n) vertices. We also construct a family of outerplanar graphs for which this bound is asymptotically tight.
Year
DOI
Venue
2009
10.1007/978-3-540-77566-9_41
Discrete & Computational Geometry
Keywords
DocType
Volume
Graph drawing,Straight-line drawing,Planarity,NP-hardness,Hardness of approximation,Moving vertices,Untangling,Point-set embeddability
Journal
42
Issue
ISSN
Citations 
4
1432-0444
9
PageRank 
References 
Authors
0.83
18
6
Name
Order
Citations
PageRank
Xavier Goaoc113820.76
Jan Kratochvíl21751151.84
Yoshio Okamoto317028.50
Chan-su Shin420626.76
Andreas Spillner520749.13
Alexander Wolff6436.65