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 \({\Omega(n^\ensuremath{\varepsilon})}\) vertices fixed for some absolute constant \(\ensuremath{\varepsilon} >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 \(\Omega(\sqrt{\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 \(\Omega(\sqrt{n})\) vertices. We also construct a family of outerplanar graphs for which this bound is asymptotically tight.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Avis, D.: Generating rooted triangulations without repetitions. Algorithmica 16, 618–632 (1996)
Bose, P., Dujmovic, V., Hurtado, F., Langerman, S., Morin, P., Wood, D.R.: A polynomial bound for untangling geometric planar graphs (October 2007), http://arxiv.org/abs/0710.1641
Erdős, P., Szekeres, G.: A combinatorial problem in geometry. Compos. Math. 2, 463–470 (1935)
Goaoc, X., Kratochvíl, J., Okamoto, Y., Shin, C.-S., Wolff, A.: Moving vertices to make drawings plane. In: Hong, S.-H., Nishizeki, T. (eds.) GD 2007. Proc. 15th Intern. Sympos. Graph Drawing. LNCS, vol. 4875, Springer, Heidelberg (to appear, 2008)
Hong, S.-H., Nagamochi, H.: Convex drawing of graphs with non-convex boundary. In: Fomin, F.V. (ed.) WG 2006. LNCS, vol. 4271, pp. 113–124. Springer, Heidelberg (2006)
Hopcroft, J., Tarjan, R.E.: Efficient planarity testing. J. ACM 21, 549–568 (1974)
Kang, M., Schacht, M., Verbitsky, O.: How much work does it take to straighten a plane graph out? (June 2007), http://arxiv.org/abs/0707.3373
Pach, J., Tardos, G.: Untangling a polygon. Discrete Comput. Geom. 28(4), 585–592 (2002)
Schensted, C.: Longest increasing and decreasing subsequences. Canadian Journal of Mathematics 13, 179–191 (1961)
Schnyder, W.: Embedding planar graphs on the grid. In: SODA 1990. Proc. 1st ACM-SIAM Symp. on Discrete Algorithms, pp. 138–148 (1990)
Spillner, A., Wolff, A.: Untangling a planar graph (September 2007), http://arxiv.org/abs/0709.0170
Tantalo, J.: Planarity (2007), http://planarity.net/
Tutte, W.T.: A theory of 3-connected graphs. Indagationes Mathematicae 23, 441–455 (1961)
Verbitsky, O.: On the obfuscation complexity of planar graphs (May & June 2007), http://arxiv.org/abs/0705.3748
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Spillner, A., Wolff, A. (2008). Untangling a Planar Graph. In: Geffert, V., Karhumäki, J., Bertoni, A., Preneel, B., Návrat, P., Bieliková, M. (eds) SOFSEM 2008: Theory and Practice of Computer Science. SOFSEM 2008. Lecture Notes in Computer Science, vol 4910. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-77566-9_41
Download citation
DOI: https://doi.org/10.1007/978-3-540-77566-9_41
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-77565-2
Online ISBN: 978-3-540-77566-9
eBook Packages: Computer ScienceComputer Science (R0)