%0 Journal Article %1 gkossw-upg-DCG09 %A Goaoc, Xavier %A Kratochvíl, Jan %A Okamoto, Yoshio %A Shin, Chan-Su %A Spillner, Andreas %A Wolff, Alexander %D 2009 %J Discrete & Computational Geometry %K NP-hardness gd-info1 graph_drawing hardness_of_approximation moving_vertices myown planarity point-set_embeddability straight-line_drawing untangling %N 4 %P 542--569 %R 10.1007/s00454-008-9130-6 %T Untangling a Planar Graph %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 $((łog 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-DCG09, 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 = {2024-10-12T23:30:06.000+0200}, author = {Goaoc, Xavier and Kratochvíl, Jan and Okamoto, Yoshio and Shin, Chan-Su and Spillner, Andreas and Wolff, Alexander}, biburl = {https://www.bibsonomy.org/bibtex/271f4272040b1a6303ef7caf7f76eddd6/awolff}, doi = {10.1007/s00454-008-9130-6}, interhash = {15e1a9a7f71b04b45192548412240a11}, intrahash = {71f4272040b1a6303ef7caf7f76eddd6}, journal = {Discrete \& Computational Geometry}, keywords = {NP-hardness gd-info1 graph_drawing hardness_of_approximation moving_vertices myown planarity point-set_embeddability straight-line_drawing untangling}, number = 4, pages = {542--569}, pdf = {http://www1.pub.informatik.uni-wuerzburg.de/pub/wolff/pub/gkossw-upg-09.pdf}, succeeds = {gkosw-mvmdp-08}, timestamp = {2024-10-12T23:30:06.000+0200}, title = {Untangling a Planar Graph}, volume = 42, year = 2009 }