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.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-25878-7_28
Classifications:M Methods > M.600 Planar
ID Code:1263

Repository Staff Only: item control page


Arkin, E.M., Held, M., Mitchell, J.S.B., Skiena, S.: Hamiltonian triangulations for fast rendering. The Visual Computer 12(9), 429–444 (1996)

Bose, P., Dujmovic, V., Hurtado, F., Langerman, S., Morin, P., Wood, D.R.: A polynomial bound for untangling geometric planar graphs. Discrete Comput. Geom. 42(4), 570–585 (2009)

Cibulka, J.: Untangling polygons and graphs. Discrete Comput. Geom. 43, 402–411 (2010)

Erdős, P., Szekeres, G.: A combinatorial problem in geometry. Compositio Mathematica 2, 463–470 (1935)

Fáry, I.: On straight line representation of planar graphs. Acta Univ. Szeged, Acta Sci. Math. 11, 229–233 (1948)

Goaoc, X., Kratochvíl,J., Okamoto, Y., Shin, C.S., Spillner, A., Wolff, A.: Untangling a planar graph. Discrete Comput. Geom. 42(4), 542–569 (2009)

Holton, D.A., McKay, B.D.: The smallest non-Hamiltonian 3-connected cubic planar graphs have 38 vertices. J. Combin. Theory Ser. B 45(3), 305–319 (1988)

Kang, M., Pikhurko, O., Ravsky, A., Schacht, M., Verbitsky, O.: Untangling planar graphs from a specified vertex position—Hard cases. Discrete Appl. Math. 159(8), 789–799 (2011)

Pach, J., Tardos, G.: Untangling a polygon. Discrete Comput. Geom. 28(4), 585–592 (2002)

Tait, P.G.: Listing’s Topologie. Philosophical Magazine 17, 30–46 (1884)

Tutte, W.T.: On Hamiltonian circuits. J. LMS 21(2), 98–101 (1946)