Untangling a Planar Graph - Archive ouverte HAL Access content directly
Journal Articles Discrete and Computational Geometry Year : 2009

## Untangling a Planar Graph

(1) , (2) , (3) , (4) , , (5)
1
2
3
4
5
Xavier Goaoc
Jan Kratochvil
• Function : Author
Yoshio Okamoto
• Function : Author
Chan-Su Shin
• Function : Author
Andreas Spillner
• Function : Author
Alexander Wolff
• Function : Author

#### Abstract

A straight-line drawing δ 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,δ) denote the minimum number of vertices that need to be moved to untangle δ. We show that shift(G,δ) 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,δ)=n−shift(G,δ) to be the maximum number of vertices of a planar n-vertex graph G that can be fixed when untangling δ. 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 δ G of G with $\ensuremath {\mathrm {fix}}(G,\delta_{G})\leq \sqrt{n-2}+1$ and an n-vertex outerplanar graph H and a drawing δ H of H with $\ensuremath {\mathrm {fix}}(H,\delta_{H})\leq2\sqrt{n-1}+1$ . Thus our algorithm is asymptotically worst-case optimal for outerplanar graphs.

### Dates and versions

inria-00431408 , version 1 (12-11-2009)

### Identifiers

• HAL Id : inria-00431408 , version 1
• DOI :

### Cite

Xavier Goaoc, Jan Kratochvil, Yoshio Okamoto, Chan-Su Shin, Andreas Spillner, et al.. Untangling a Planar Graph. Discrete and Computational Geometry, 2009, 42 (4), pp.542-569. ⟨10.1007/s00454-008-9130-6⟩. ⟨inria-00431408⟩

### Export

BibTeX TEI Dublin Core DC Terms EndNote Datacite

114 View