TL;DR
This paper tackles the challenge of making non-planar graph drawings "tidy" by introducing a technique called "vertex splitting." They show that while making abstract graphs planar with vertex splits is computationally hard, it can be efficiently solved for a fixed number of splits (FPT). Crucially, they extend this to drawings in 2D space, proving that re-embedding split vertices while preserving the existing drawing is NP-complete, but offering an FPT solution for a specific subproblem.
What Problem Does This Paper Address?
Visualizing large and complex graphs is a common problem in many fields, from biology to social networks. Often, these graphs are inherently non-planar, meaning they cannot be drawn without edges crossing. These crossings create visual clutter, making it difficult to understand the graph's structure. While many methods exist to reduce crossings, this paper focuses on a specific operation: vertex splitting. A vertex split takes a single vertex and replaces it with two new vertices, distributing the original vertex's connections between them. This operation can help untangle edges and potentially lead to a planar drawing.
The paper addresses two main problems:
- Abstract Splitting Number: How many vertex splits are minimally required to make any graph planar? This is known to be NP-complete, but the authors provide a fixed-parameter tractable (FPT) algorithm, meaning it's efficient if the number of splits is small.
- Embedded Splitting Number: Given a graph already drawn in 2D space, how can we make its drawing planar using vertex splits, while keeping the existing vertices and edges in their original positions as much as possible? This is crucial for maintaining layout stability and understanding changes. They show this problem is NP-complete and break it down into two subproblems: selecting which vertices to split and then re-embedding the new vertices. For the re-embedding subproblem, they present an FPT algorithm.
Methods
The paper employs a combination of theoretical computer science techniques:
- Fixed-Parameter Tractability (FPT): For the abstract splitting number problem, they leverage existing results on minor-closed graph classes and a bounded search tree approach to achieve an FPT algorithm. This means the algorithm's runtime is exponential only in the parameter (number of splits), not the graph size.
- NP-Completeness Proofs: They prove the NP-completeness of the embedded splitting number problem and its subproblems using reductions from known NP-complete problems like Vertex Cover and Face Cover.
- Dynamic Programming on Sphere-Cut Decomposition: For the re-embedding subproblem, they develop a sophisticated FPT algorithm. This involves:
- Reducing to 10k-Outerplanarity: Transforming the input drawing into a special type of graph that is "almost planar."
- Sphere-Cut Decomposition: Decomposing the graph into a tree structure, allowing for a structured, bottom-up dynamic programming approach.
- Signatures: Developing a complex "signature" system to represent partial solutions at each node of the decomposition tree, capturing crucial information about embedded copies and missing connections.
- Branching Rules: Using branching rules to explore different possibilities for splitting and re-embedding vertices.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Vertex Splitting in Drawings is Hard: While vertex splitting is a useful operation for abstract graphs, applying it to existing drawings introduces significant complexity, making the problem NP-complete. This is because the fixed positions of existing elements constrain where new vertices can be placed.
- Parameterizing by Splits is Key: The core of their algorithmic success lies in parameterizing the problem by the number of vertex splits. This allows for efficient solutions (FPT) even though the problem is NP-complete in general.
- Sophisticated Dynamic Programming for Re-embedding: The dynamic programming approach on sphere-cut decompositions is a powerful technique for handling the geometric constraints of re-embedding vertices in a drawing. The "signature" concept is particularly novel for summarizing the state of partial solutions.
- Bridging Theory and Practice: The paper connects theoretical concepts like graph minors and outerplanarity to practical problems in graph visualization.
Key Results
- Abstract Splitting Number: A non-uniform FPT algorithm for the splitting number problem parameterized by the number of splits.
- Embedded Splitting Number: NP-completeness for the embedded splitting number problem and its subproblems (candidate selection and re-embedding).
- Split Set Re-Embedding: An FPT algorithm for the re-embedding subproblem, running in $2^{O(k^2)} \cdot n^{O(1)}$ time, where $k$ is the number of splits and $n$ is the number of vertices. This algorithm relies on reducing the problem to 10k-outerplanarity and using dynamic programming on a sphere-cut decomposition.
- Optimally Splitting a Single Vertex: A polynomial-time algorithm for minimizing crossings when splitting a single vertex into $k$ copies, parameterized by $k$.
Limitations and Future Work
- NP-Completeness of Embedded Splitting Number: The main open problem highlighted is the NP-completeness of the overall embedded splitting number problem. While they have an FPT solution for re-embedding, the candidate selection part remains NP-complete.
- Variations of Vertex Splitting: The authors suggest exploring variations of vertex splitting, such as:
- Crossing Minimization: Using vertex splitting not just for planarity but also for minimizing crossings.
- Different Costs: Adapting the splitting operation to have different costs for splitting and re-embedding.
- Practical Implementation: While the algorithms are theoretically sound, their complexity might pose challenges for direct implementation on very large graphs. Further research into practical implementations and heuristics would be valuable.
Summary updated