TY - GEN

T1 - Moving vertices to make drawings plane

AU - Goaoc, X.

AU - Kratochvil, J.

AU - Okamoto, Y.

AU - Shin, C.S.

AU - Wolff, A.

PY - 2008

Y1 - 2008

N2 - 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.
This work was started on the 9th "Korean" Workshop on Computational Geometry and Geometric Networks organized by A. Wolff and X. Goaoc, July 30–August 4, 2006 in Schloß Dagstuhl, Germany. Further contributions were made at the 2nd Workshop on Graph Drawing and Computational Geometry organized by W. Didimo and G. Liotta, March 11–16, 2007 in Bertinoro, Italy.

AB - 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.
This work was started on the 9th "Korean" Workshop on Computational Geometry and Geometric Networks organized by A. Wolff and X. Goaoc, July 30–August 4, 2006 in Schloß Dagstuhl, Germany. Further contributions were made at the 2nd Workshop on Graph Drawing and Computational Geometry organized by W. Didimo and G. Liotta, March 11–16, 2007 in Bertinoro, Italy.

U2 - 10.1007/978-3-540-77537-9_13

DO - 10.1007/978-3-540-77537-9_13

M3 - Conference contribution

SN - 978-3-540-77536-2

T3 - Lecture Notes in Computer Science

SP - 101

EP - 112

BT - Graph Drawing (15th International Symposium, GD'07, Sydney, Australia, September 23-26, 2007, Revised Papers)

A2 - Hong, S.K.

A2 - Nishizeki, T.

A2 - Quan, W.

PB - Springer

CY - Berlin

ER -