2007/05/25 by Oleg Verbitsky, Verbitsky, Oleg
Computer Science · Mathematics · #Advanced Graph Theory Research #Bounded function #Combinatorics #Computational Complexity (cs.CC) #Computational Geometry and Mesh Generation #Discrete Mathematics (cs.DM) #Discrete mathematics #FOS: Computer and information sciences #Graph #Limits and Structures in Graph Theory #Mathematics #Planar graph #Time complexity #Vertex (graph theory) #cs.CC #cs.DM
paper · pdf · doi:10.48550/arxiv.0705.3748
12 pages, 1 figure. The proof of Theorem 3 is simplified. An overview of a related work is added
openalex publication_date 2007/05/25 · arxiv created 2007/12/14 · arxiv updated 2011/11/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06
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 (δ(G)2/24-o(1))n2 < \obf G <3 n2 for an n-vertex planar graph G with minimum vertex degree δ(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 δ(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 δ(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.