Planarizing Graphs and their Drawings by Vertex Splitting

Soeren Nickel, Martin Nöllenburg, Manuel Sorge, Anaïs Villedieu, Hsiang-Yun Wu, Jules WulmsGD 2022 · OpenReview

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:

  1. 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.
  2. 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

Abstract

The splitting number of a graph $G=(V,E)$ is the minimum number of vertex splits required to turn $G$ into a planar graph, where a vertex split removes a vertex $v \in V$, introduces two new vertices $v_1, v_2$, and distributes the edges formerly incident to $v$ among its two split copies $v_1, v_2$. The splitting number problem is known to be NP-complete. In this paper we shift focus to the splitting number of graph drawings in $\mathbb R^2$, where the new vertices resulting from vertex splits can be re-embedded into the existing drawing of the remaining graph. We first provide a non-uniform fixed-parameter tractable (FPT) algorithm for the splitting number problem (without drawings). Then we show the NP-completeness of the splitting number problem for graph drawings, even for its two subproblems of (1) selecting a minimum subset of vertices to split and (2) for re-embedding a minimum number of copies of a given set of vertices. For the latter problem we present an FPT algorithm parameterized by the number of vertex splits. This algorithm reduces to a bounded outerplanarity case and uses an intricate dynamic program on a sphere-cut decomposition.
BibTeX
@inproceedings{nickel2022planarizing,
  author = {Soeren Nickel and Martin Nöllenburg and Manuel Sorge and Anaïs Villedieu and Hsiang-Yun Wu and Jules Wulms},
  title = {{Planarizing Graphs and their Drawings by Vertex Splitting}},
  booktitle = {GD},
  year = {2022},
  url = {https://openreview.net/forum?id=69tF0lqYqw},
}
Figure