On the obfuscation complexity of planar graphs

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 , the obfuscation complexity of G, to be the maximum number of edge crossings in a drawing of G. Relating to the distribution of vertex degrees in G, we show an efficient way of constructing a drawing of G with at least edge crossings. We prove bounds for an n-vertex planar graph G with minimum vertex degree δ(G)≥2.The shift complexity of G, denoted by , 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 δ(G)≥3, then is linear in the number of vertices due to the known fact that the matching number of G is linear. However, in the case δ(G)≥2 we notice that 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.