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. In: Graph Drawing 15th International Symposium, GD 2007, September 24-26, 2007 , pp. 101-112(Official URL: http://dx.doi.org/10.1007/978-3-540-77537-9_13).

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
Additional Information: 10.1007/978-3-540-77537-9_13
Classifications: P Styles > P.540 Planar
M Methods > M.300 Dynamic / Incremental / Online
URI: http://gdea.informatik.uni-koeln.de/id/eprint/832

Actions (login required)

View Item View Item