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 @math vertices when untangling a drawing of an n-vertex graph G. If G is outerplanar, the same algorithm fixes at least @math vertices. On the other hand, we construct, for arbitrarily large n, an n-vertex planar graph G and a drawing δ G of G with @math and an n-vertex outerplanar graph H and a drawing δ H of H with @math . Thus our algorithm is asymptotically worst-case optimal for outerplanar graphs.
The hardness of computing @math given @math and @math was obtained independently by Verbitsky @cite_22 by a reduction from independent set in line-segment intersection graphs. While our proof is more complicated than his, it is stronger as it also yields hardness of approximation and extends to the problem with given vertex--point correspondence.
@cite_22
2080201242
Being motivated by John Tantalo's Planarity Game, we consider straight line plane drawings of a planar graph G with edge crossings and wonder how obfuscated such drawings can be. We define obf(G), the obfuscation complexity of G, to be the maximum number of edge crossings in a drawing of G. Relating obf(G) to the distribution of vertex degrees in G, we show an efficient way of constructing a drawing of G with at least obf(G) 3 edge crossings. We prove bounds (@d(G)^2 24-o(1))n^2@?obf(G) =2. The shift complexity of G, denoted by shift(G), is the minimum number of vertex shifts sufficient to eliminate all edge crossings in an arbitrarily obfuscated drawing of G (after shifting a vertex, all incident edges are supposed to be redrawn correspondingly). If @d(G)>=3, then shift(G) is linear in the number of vertices due to the known fact that the matching number of G is linear. However, in the case @d(G)>=2 we notice that shift(G) can be linear even if the matching number is bounded. As for computational complexity, we show that, given a drawing D of a planar graph, it is NP-hard to find an optimum sequence of shifts making D crossing-free.