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 , pp. 290-295(Official URL: http://dx.doi.org/ 10.1007/978-3-642-25878-7_28).

Full text not available from this repository.

Abstract

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.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-642-25878-7_28
Classifications: M Methods > M.600 Planar
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1263

Actions (login required)

View Item View Item