Abstract
This paper introduces and explores $k$-gap-planar graphs, a new family of graphs inspired by the practical need to make complex network visualizations more readable. By formalizing the concept of "edge casing"—where one edge appears to pass under another at a crossing—the authors provide a rigorous mathematical framework for a common technique in graphic design and information visualization.
Introduction
In graph drawing, crossings are the primary obstacle to readability. While planar graphs (which have no crossings) are ideal, most real-world networks are non-planar. Researchers in the field of "beyond planarity" seek ways to allow crossings while maintaining some level of visual order. A common practical solution is edge casing: when two edges cross, a small "gap" is introduced in one edge to show that the other edge passes over it. This reduces visual clutter. However, if an edge has too many gaps, it becomes difficult for the human eye to follow.
The authors address the lack of a formal model for this: how many edges can a graph have if we limit the number of gaps per edge? How does this constraint change the fundamental properties of the graph? They define $k$-gap-planar graphs as those where each crossing is "charged" to only one of the two involved edges, and no edge is charged more than $k$ times.
Methodology
The authors employ a combination of combinatorial geometry, graph theory, and computational complexity analysis to characterize this new class:
- Hall’s Marriage Theorem: This classic result is used to characterize $k$-gap-planarity. A drawing is $k$-gap-planar if and only if every subset of edges $E'$ has at most $k \cdot |E'|$ crossings among them.
- Charging Schemes: To determine the maximum edge density, they employ a "charging scheme" on triangulated drawings, a standard technique in topological graph theory.
- Reduction from 3PARTITION: To prove that the recognition problem is NP-complete, they construct a complex "gadget" graph that can only be drawn in a 1-gap-planar way if a specific numerical partitioning problem has a solution.
Key Insights
The paper provides several critical observations that connect gap-planarity to existing graph theory:
- Non-Symmetric Constraints: Unlike $k$-planar graphs (where every crossing counts against both edges), $k$-gap-planarity is non-symmetric. You only "pay" for a crossing on one of the two edges. This aligns the mathematics with the visual practice of edge casing.
- The Pseudoarboricity Link: The authors show that a drawing is $k$-gap-planar if and only if its "crossing graph" has a pseudoarboricity of at most $k$.
- Density vs. Planarity: A 1-gap-planar graph can have up to $5n - 10$ edges (where $n$ is the number of vertices). This is significantly denser than standard planar graphs ($3n - 6$), showing that allowing even one gap per edge dramatically increases the complexity of representable networks.
- Hierarchy Placement: The paper establishes a nesting: every $2k$-planar graph is $k$-gap-planar, and every $k$-gap-planar graph is $(2k+2)$-quasiplanar.
Key Results
The study establishes several fundamental properties of these graphs:
- Density Bounds: For general $k$, the number of edges is $O(\sqrt{k} \cdot n)$. For $k=1$, the tight bound is exactly $5n - 10$ for graphs with $n \geq 20$.
- Complete Graphs: The complete graph $K_n$ is 1-gap-planar if and only if $n \leq 8$.
- Computational Complexity: Deciding if a graph is 1-gap-planar is NP-complete. This remains true even if the "rotation system" (the clockwise order of edges around each vertex) is fixed.
Conclusion and Future Work
While this work provides a solid foundation for $k$-gap-planar graphs, several avenues remain open for future research:
- Tightness for $k > 1$: Finding the exact constants for the density of $k$-gap-planar graphs for $k \geq 2$ remains an open challenge.
- Geometric Constraints: Future work could investigate straight-line drawings or drawings with right-angle crossings (RAC) under the gap-planar constraint.
- Treewidth: The treewidth of $k$-gap-planar graphs is still an open question.
- Practical Algorithms: Since the general recognition problem is NP-complete, future work could look for approximation algorithms or heuristics that work well on real-world data.
Summary updated