Moving vertices to make drawings plane - Archive ouverte HAL Access content directly
Conference Papers Year : 2007

Moving vertices to make drawings plane

(1) , (2) , (3) , (4) , (5)
1
2
3
4
5

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.
Fichier principal
Vignette du fichier
Vertex-move-gd07.pdf (202.67 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

inria-00181775 , version 1 (12-11-2009)

Identifiers

Cite

Xavier Goaoc, Jan Kratochvil, Yoshio Okamoto, Chan-Su Shin, Alexander Wolff. Moving vertices to make drawings plane. 15th International Symposium on Graph Drawing, Sep 2007, Sydney, Australia. pp.101-112, ⟨10.1007/978-3-540-77537-9_13⟩. ⟨inria-00181775⟩
129 View
188 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More