Well-Formed Separator Sequences, with an Application to Hypergraph Drawing

René van Bevern, Iyad A. Kanj, Christian Komusiewicz, Rolf Niedermeier, Manuel SorgearXiv 2015 · arXiv

Introduction

Representing hypergraphs—structures where edges can connect arbitrary sets of vertices—is a fundamental challenge in data visualization. A common technique for rendering these relationships is the subdivision drawing, which represents vertices as regions and hyperedges as larger connected regions containing them. This task is mathematically equivalent to finding a planar support: a planar graph $G$ where each hyperedge $S$ corresponds to a connected subgraph. This paper explores the theoretical foundations of these supports, providing a new algorithmic framework for their construction.

The Complexity of Planar Supports and the "Twin Trap"

Determining the existence of a planar support is known to be NP-complete. A significant contribution of this paper is identifying the "Twin Trap." While previous research often simplified the problem by removing "twins" (vertices belonging to the exact same sets of hyperedges), the authors prove that twins are often necessary for a support to remain planar. Removing them can transform a solvable instance into an unsolvable one.

Consequently, the problem requires a more nuanced approach using Parameterized Complexity. The authors focus on finding an algorithm that is Fixed-Parameter Tractable (FPT) relative to the number of hyperedges ($m$) and the graph's outerplanarity ($r$), which measures the "depth" of the graph's embedding.

Methodology: Well-Formed Separator Sequences

The authors introduce well-formed separator sequences to decompose large $r$-outerplanar graphs. This structural tool allows for the systematic reduction of complex graphs while preserving their support properties.

Structural decomposition of a planar support using separator sequences.

The methodology relies on three pillars:

  1. Slicing: Decomposing the graph into a sequence of separators, which are typically paths or cycles that behave predictably.
  2. Signatures: Assigning a "signature" to each separator based on how hyperedges traverse it. These signatures act as a topological summary, ensuring that connectivity requirements are maintained during compression.
  3. Gluing Lemma: A reduction rule stating that if two separators in a long sequence share the same signature, the intervening graph segment is redundant and can be "glued" away without changing the hypergraph's support properties.

Key Theoretical Results

The paper culminates in two major theoretical findings that establish the feasibility of this approach:

  • Theorem 3.2: Every $r$-outerplanar triangulated disk with $n$ vertices contains a well-formed separator sequence of length at least $\lfloor \sqrt[2r]{\log(n)}/6^r \rfloor$. This ensures that sufficiently large graphs always possess the structural redundancy needed for reduction.
  • Theorem 4.7: The Planar Support problem admits a problem kernel. This means any instance can be reduced to an equivalent version with a size bounded by a function of $m$ and $r$, independent of the total number of vertices $n$.

These results provide the first explicit, uniform FPT algorithm for the problem, offering a constructive path toward solving instances that were previously considered intractable.

Conclusion

By inventing well-formed separator sequences, the authors have bridged a gap in hypergraph theory. Although the resulting problem kernel is currently very large—characterized as a "tower of exponents"—the work establishes a rigorous foundation for future optimizations. Future research may focus on refining these sequences for non-triangulated graphs or extending the technique to find edge-minimal supports, further enhancing the clarity of complex data visualizations.

Summary updated

Abstract

Given a hypergraph $H$, the Planar Support problem asks whether there is a planar graph $G$ on the same vertex set as $H$ such that each hyperedge induces a connected subgraph of $G$. Planar Support is motivated by applications in graph drawing and data visualization. We show that Planar Support is fixed-parameter tractable when parameterized by the number of hyperedges in the input hypergraph and the outerplanarity number of the sought planar graph. To this end, we develop novel structural results for $r$-outerplanar triangulated disks, showing that they admit sequences of separators with structural properties enabling data reduction. This allows us to obtain a problem kernel for Planar Support, thus showing its fixed-parameter tractability.
BibTeX
@misc{bevern2015well,
  author = {René van Bevern and Iyad A. Kanj and Christian Komusiewicz and Rolf Niedermeier and Manuel Sorge},
  title = {{Well-Formed Separator Sequences, with an Application to Hypergraph Drawing}},
  year = {2015},
  eprint = {1507.02350},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1507.02350},
}
Figure