Name
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 1BENDPOINTSETEMBED- DABILITY, which yields similar results for that problem. Third, we give bounds for the behavior of MINMOVEDVERTICES on trees and general planar graphs. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1007/978-3-540-77537-9_13 | Clinical Orthopaedics and Related Research |
Keywords | DocType | Volume |
related problem minmovedvertices,drawing plane,similar result,on-line game,planar graph,minimum number,john tantalo,drawings plane,non-plane straight-line drawing,general planar graph,graph-drawing problem | Conference | abs/0706.1002 |
ISSN | ISBN | Citations |
0302-9743 | 3-540-77536-6 | 7 |
PageRank | References | Authors |
0.81 | 8 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Xavier Goaoc | 1 | 138 | 20.76 |
| Jan Kratochvíl | 2 | 1751 | 151.84 |
| Yoshio Okamoto | 3 | 170 | 28.50 |
| Chan-su Shin | 4 | 206 | 26.76 |
| Alexander Wolff | 5 | 222 | 22.66 |