Untangling a Planar Graph - Computer Science > Computational GeometryReport as inadecuate

Untangling a Planar Graph - Computer Science > Computational Geometry - Download this document for free, or read online. Document in PDF available to download.

Abstract: A straight-line drawing $\delta$ of a planar graph $G$ need not be plane, butcan be made so by \emph{untangling} it, that is, by moving some of the verticesof $G$. Let shift$G,\delta$ denote the minimum number of vertices that needto be moved to untangle $\delta$. We show that shift$G,\delta$ is NP-hard tocompute and to approximate. Our hardness results extend to a version of\textsc{1BendPointSetEmbeddability}, a well-known graph-drawing problem.Further we define fix$G,\delta=n-shiftG,\delta$ to be the maximum numberof 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 theother 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$ andan $n$-vertex outerplanar graph $H$ and a drawing $\delta H$ of $H$ withfix$H,\delta H \le 2 \sqrt{n-1}+1$. Thus our algorithm is asymptoticallyworst-case optimal for outerplanar graphs.

Author: Xavier Goaoc, Jan Kratochvil, Yoshio Okamoto, Chan-Su Shin, Andreas Spillner, Alexander Wolff

Source: https://arxiv.org/

Related documents