A straight-line drawing $\delta$ of a planar graph $G$ need not be plane, but can be made so by untangling it, that is, by moving some of the vertices of $G$. Let shift$(G,\delta)$ denote the minimum number of vertices that need to be moved to untangle $\delta$. We show that shift$(G,\delta)$ is NP-hard to compute and to approximate. Our hardness results extend to a version of 1BendPointSetEmbeddability, a well-known graph-drawing problem. Further we define fix$(G,\delta)=n-shift(G,\delta)$ to be the maximum number of vertices of a planar $n$-vertex graph $G$ that can be fixed when untangling $\delta$. We give an algorithm that fixes at least $((n)-1)/n$ vertices when untangling a drawing of an $n$-vertex graph $G$. If $G$ is outerplanar, the same algorithm fixes at least $n/2$ vertices. On the other hand we construct, for arbitrarily large $n$, an $n$-vertex planar graph $G$ and a drawing $\delta_G$ of $G$ with fix$(G,\delta_G) n-2+1$ and an $n$-vertex outerplanar graph $H$ and a drawing $\delta_H$ of $H$ with fix$(H,\delta_H) 2 n-1+1$. Thus our algorithm is asymptotically worst-case optimal for outerplanar graphs.
%0 Journal Article
%1 gkossw-upg-09
%A Goaoc, Xavier
%A Kratochvíl, Jan
%A Okamoto, Yoshio
%A Shin, Chan-Su
%A Spillner, Andreas
%A Wolff, Alexander
%D 2009
%J #DCG#
%K planarity untangling straight-linedrawing point-setembeddability. Graphdrawing movingvertices hardnessofapproxi-mation NP-hardness
%N 4
%P 542--569
%R 10.1007/s00454-008-9130-6
%T Untangling a Planar Graph
%U http://dx.doi.org/10.1007/s00454-008-9130-6
%V 42
%X A straight-line drawing $\delta$ of a planar graph $G$ need not be plane, but can be made so by untangling it, that is, by moving some of the vertices of $G$. Let shift$(G,\delta)$ denote the minimum number of vertices that need to be moved to untangle $\delta$. We show that shift$(G,\delta)$ is NP-hard to compute and to approximate. Our hardness results extend to a version of 1BendPointSetEmbeddability, a well-known graph-drawing problem. Further we define fix$(G,\delta)=n-shift(G,\delta)$ to be the maximum number of vertices of a planar $n$-vertex graph $G$ that can be fixed when untangling $\delta$. We give an algorithm that fixes at least $((n)-1)/n$ vertices when untangling a drawing of an $n$-vertex graph $G$. If $G$ is outerplanar, the same algorithm fixes at least $n/2$ vertices. On the other hand we construct, for arbitrarily large $n$, an $n$-vertex planar graph $G$ and a drawing $\delta_G$ of $G$ with fix$(G,\delta_G) n-2+1$ and an $n$-vertex outerplanar graph $H$ and a drawing $\delta_H$ of $H$ with fix$(H,\delta_H) 2 n-1+1$. Thus our algorithm is asymptotically worst-case optimal for outerplanar graphs.
@article{gkossw-upg-09,
abstract = {A straight-line drawing $\delta$ of a planar graph $G$ need not be plane, but can be made so by \emph{untangling} it, that is, by moving some of the vertices of $G$. Let shift$(G,\delta)$ denote the minimum number of vertices that need to be moved to untangle $\delta$. We show that shift$(G,\delta)$ is NP-hard to compute and to approximate. Our hardness results extend to a version of \textsc{1BendPointSetEmbeddability}, a well-known graph-drawing problem. \par Further we define fix$(G,\delta)=n-shift(G,\delta)$ to be the maximum number of vertices of a planar $n$-vertex graph $G$ that can be fixed when untangling $\delta$. We give an algorithm that fixes at least $\sqrt{((\log n)-1)/\log \log n}$ vertices when untangling a drawing of an $n$-vertex graph $G$. If $G$ is outerplanar, the same algorithm fixes at least $\sqrt{n/2}$ vertices. On the other hand we construct, for arbitrarily large $n$, an $n$-vertex planar graph $G$ and a drawing $\delta_G$ of $G$ with fix$(G,\delta_G) \le \sqrt{n-2}+1$ and an $n$-vertex outerplanar graph $H$ and a drawing $\delta_H$ of $H$ with fix$(H,\delta_H) \le 2 \sqrt{n-1}+1$. Thus our algorithm is asymptotically worst-case optimal for outerplanar graphs.},
added-at = {2010-04-13T09:41:24.000+0200},
author = {Goaoc, Xavier and Kratochv{\'i}l, Jan and Okamoto, Yoshio and Shin, Chan-Su and Spillner, Andreas and Wolff, Alexander},
biburl = {https://www.bibsonomy.org/bibtex/2491f1529b80020aed9bae074fbe823ae/fink},
doi = {10.1007/s00454-008-9130-6},
interhash = {228a5bbbf400d32e2b9f006d8673a018},
intrahash = {491f1529b80020aed9bae074fbe823ae},
journal = {#DCG#},
keywords = {planarity untangling straight-linedrawing point-setembeddability. Graphdrawing movingvertices hardnessofapproxi-mation NP-hardness},
number = 4,
pages = {542--569},
pdf = {#AWPUBURL#gkossw-upg-09.pdf},
succeeds = {gkosw-mvmdp-08},
timestamp = {2010-04-13T09:41:24.000+0200},
title = {Untangling a Planar Graph},
url = {http://dx.doi.org/10.1007/s00454-008-9130-6},
volume = 42,
year = 2009
}