Upper Bound Constructions for Untangling Planar Geometric Graphs
Cano, Javier and Tóth, Csaba D. and Urrutia, Jorge (2012) Upper Bound Constructions for Untangling Planar Geometric Graphs. In: Graph Drawing 19th International Symposium, GD 2011, September 21-23, 2011, Eindhoven, The Netherlands , pp. 290-295 (Official URL: http://dx.doi.org/ 10.1007/978-3-642-25878-7_28).
Full text not available from this repository.
For every n ∈ N, there is a straight-line drawing Dn of a planar graph on n vertices such that in any crossing-free straight-line drawing of the graph, at most O(n.4982 ) vertices lie at the same position as in Dn . This improves on an earlier bound of O( √ n) by Goaoc et al.
Repository Staff Only: item control page