Logo

Login

Moving Vertices to Make Drawings Plane

Goaoc, Xavier and Kratochvíl, Jan and Okamoto, Yoshio and Shin, Chan-Su and Wolff, Alexander (2008) Moving Vertices to Make Drawings Plane. [Conference Paper]

Full text not available from this repository.

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. In this paper we investigate the related problem MinMovedVertices which asks for the minimum number of vertex moves. First, we show that MinMovedVertices is NP-hard and hard to approximate. Second, we establish a connection to the graph-drawing problem 1BendPointSetEmbeddability, which yields similar results for that problem. Third, we give bounds for the behavior of MinMovedVertices on trees and general planar graphs.

Item Type:Conference Paper
Classifications:P Styles > P.540 Planar
M Methods > M.300 Dynamic / Incremental / Online
ID Code:832
Deposited By:GDEA, Administration
Deposited On:24 Jun 2008
Last Modified:18 Sep 2008 13:09
Alternative Locations:http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=4875&spage=101

Repository Staff Only: item control page

References

1. P. Erdös and G. Szekeres. A combinatorial problem in geometry. Compos. Math., 2:463-470, 1935.

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

3. X. Goaoc, J. Kratochvíl, Y. Okamoto, C.-S. Shin, and A. Wolff. Moving vertices to make drawings plane, June 2007. Available at http://arxiv.org/abs/0706.1002.

4. M. Kang, M. Schacht, and O. Verbitsky. How much work does it take to straighten a plane graph out?, June 2007. Available at http://arxiv.org/abs/0707.3373.

5. M. Kaufmann and R. Wiese. Embedding vertices at points: Few bends suffice for planar graphs. J. Graph Algorithms Appl., 6(1):115-129, 2002.

6. D. E. Knuth and A. Raghunathan. The problem of compatible representatives. SIAM J. Discr. Math., 5(3):422-427, 1992.

7. D. Lichtenstein. Planar formulae and their uses. SIAM J. Comput., 11(2):329-343, 1982.

8. K. Misue, P. Eades, W. Lai, and K. Sugiyama. Layout adjustment and the mental map. J. Visual Languages and Computing, 6(2):183-210, June 1995.

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

10. C. Schensted. Longest increasing and decreasing subsequences. Canadian Journal of Mathematics, 13:179-191, 1961.

11. A. Spillner and A. Wolff. Untangling a planar graph, Sept. 2007. Available at http://arxiv.org/abs/0709.0170.

12. S. K. Stein. Convex maps. Proc. Amer. Math. Soc., 2:464-466, 1951.

13. J. Tantalo. Planarity. Web site at http://planarity.net/, accessed May 21, 2007.

14. O. Verbitsky. On the obfuscation complexity of planar graphs, May & June 2007. Available at http://arxiv.org/abs/0705.3748.

15. K. Wagner. Bemerkungen zum Vierfarbenproblem. Jahresbericht Deutsch. Math.-Verein., 46:26-32, 1936.

GDEA is powered by EPrints 3 which is developed by the School of Electronics and Computer Science at the University of Southampton. More information and software credits.