Moving Vertices to Make Drawings Plane
| dc.creator | Goaoc, Xavier | |
| dc.creator | Kratochvil, Jan | |
| dc.creator | Okamoto, Yoshio | |
| dc.creator | Shin, Chan-Su | |
| dc.creator | Wolff, Alexander | |
| dc.date | 2007-06-07 | |
| dc.date | 2008-11-06 | |
| dc.date.accessioned | 2026-07-07T10:15:30Z | |
| dc.date.available | 2026-07-07T10:15:30Z | |
| dc.description | A straight-line drawing $δ$ of a planar graph $G$ need not be plane, but can be made so by moving some of the vertices. Let shift$(G,δ)$ denote the minimum number of vertices that need to be moved to turn $δ$ into a plane drawing of $G$. We show that shift$(G,δ)$ is NP-hard to compute and to approximate, and we give explicit bounds on shift$(G,δ)$ when $G$ is a tree or a general planar graph. Our hardness results extend to 1BendPointSetEmbeddability, a well-known graph-drawing problem. | |
| dc.description | This paper has been merged with http://arxiv.org/abs/0709.0170 | |
| dc.identifier | https://arxiv.org/abs/0706.1002 | |
| dc.identifier | http://arxiv.org/abs/0706.1002 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/173193 | |
| dc.subject | Computational Geometry | |
| dc.subject | Computational Complexity | |
| dc.subject | Discrete Mathematics | |
| dc.title | Moving Vertices to Make Drawings Plane | |
| dc.type | text |