Moving vertices to make drawings plane

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.
Type de document :
Communication dans un congrès
15th International Symposium on Graph Drawing, Sep 2007, Sydney, Australia. Springer, 4875/2008, pp.101-112, 2007, Lecture Notes in Computer Science. 〈http://www.springerlink.com/content/515132482g137207/〉. 〈10.1007/978-3-540-77537-9_13〉
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00181775
Contributeur : Xavier Goaoc <>
Soumis le : jeudi 12 novembre 2009 - 19:11:49
Dernière modification le : mercredi 26 septembre 2018 - 21:52:01
Document(s) archivé(s) le : lundi 24 septembre 2012 - 14:31:15

Fichier

Vertex-move-gd07.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

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. Springer, 4875/2008, pp.101-112, 2007, Lecture Notes in Computer Science. 〈http://www.springerlink.com/content/515132482g137207/〉. 〈10.1007/978-3-540-77537-9_13〉. 〈inria-00181775〉

Partager

Métriques

Consultations de la notice

311

Téléchargements de fichiers

180