Twins in Subdivision Drawings of Hypergraphs

René van Bevern, Iyad A. Kanj, Christian Komusiewicz, Rolf Niedermeier, Manuel Sorge

Abstract: Subdivision drawings represent hypergraphs by partitioning the plane into regions for each vertex. While "twin" vertices—those belonging to the same set of hyperedges—were long considered redundant in these drawings, this paper proves they can be essential for planarity. By establishing a mathematical bound on the number of necessary twins, the authors provide a linear-time algorithm for finding drawings with a fixed number of layers.

What Problem Does This Paper Address?

Hypergraphs are a powerful way to model complex relationships (sets of sets), but visualizing them is notoriously difficult. One elegant method is the subdivision drawing, where the plane is divided into regions representing vertices. For a hypergraph to be "drawable" in this style, the regions belonging to any single hyperedge must form a single, connected area.

A subdivision drawing of a hypergraph. The left panel shows hyperedges as overlapping sets; the right panel shows the corresponding subdivision where vertices are regions.

In graph theory, twins are pairs of vertices that belong to exactly the same set of hyperedges. Previous research often assumed twins were irrelevant: if you could draw a hypergraph with one twin, surely you could just "split" that region to accommodate the second. This paper tackles two main challenges:

  1. The Twin Fallacy: Proving that twins are actually necessary for some subdivision drawings to exist.
  2. The Complexity Gap: Determining if the problem of finding these drawings is computationally tractable when the number of hyperedges is small.

Methods

The authors bridge the gap between visualization and graph theory by using the concept of a planar support. A support is a graph where the vertices are the same as the hypergraph, and every hyperedge induces a connected subgraph. If a hypergraph has a planar support, it has a subdivision drawing.

The core of their approach involves:

  • $r$-Outerplanarity: They focus on supports that are $r$-outerplanar, meaning the graph can be drawn in "layers" (like an onion) with a maximum depth of $r$.
  • Data Reduction Rules: They define a specific function, $\psi(m, r)$, which acts as a "safety threshold." If a group of twins is larger than this threshold, the extra vertices are truly redundant and can be removed without changing whether the hypergraph is drawable.
  • Signature Analysis: To prove this threshold exists, they use "edge-bipartition signatures" and "nested separators." This allows them to show that in a sufficiently large graph, certain structures must repeat, meaning some vertices aren't contributing anything unique to the graph's planarity.

Key Insights and Ideas

  • Twins are Structural Conduits: The authors provide a clever counter-example where two twins act as separate "conduits" to connect different parts of the drawing. Removing one twin breaks the connectivity required for the hyperedges, making the drawing impossible.
A planar support graph illustrating how specific vertex configurations, including twins, are necessary to maintain the connectivity of hyperedges in a planar drawing.
  • Kernelization: By proving that any "twin class" (a group of identical vertices) only needs a finite number of members to preserve drawability, they effectively "shrink" the problem. This is a classic technique in parameterized complexity called kernelization.
  • Fixed-Parameter Tractability (FPT): They show that while the problem is generally NP-complete, it becomes solvable in linear time ($O(n)$) if the number of hyperedges ($m$) and the number of layers ($r$) are kept constant.

Key Results

  • Theorem 1: The authors present a linear-time algorithm for the $r$-Outerplanar Support problem for constant $m$ and $r$.
  • The Bound: They derive an explicit (though massive) upper bound for the number of necessary twins: $$\psi(m, r) = 2^{6r \cdot 2^m \cdot (2r^2+r+1) \cdot (r+1)^{32r^2+8r}}$$
  • Theoretical Correction: The paper successfully refutes the long-standing assumption in the field that hypergraphs can be assumed to be "twinless" without loss of generality.

Limitations and Future Work

  • The "Galactic" Constant: While the algorithm is technically linear-time, the constant factor determined by $\psi(m, r)$ grows astronomically fast. As the authors admit, this result is currently more of a theoretical classification than a practical tool for large hypergraphs.
  • General Planarity: The current FPT result requires a fixed $r$ (number of layers). A major open question is whether the problem remains FPT for general planar supports where $r$ can be anything.
  • Practical Heuristics: Future work could focus on finding much smaller, more practical data reduction rules that could be used in real-world visualization software.

Summary updated

Abstract

Visualizing hypergraphs, systems of subsets of some universe, has continuously attracted research interest in the last decades. We study a natural kind of hypergraph visualization called subdivision drawings. Dinkla et al. [Comput. Graph. Forum ’12] claimed that only few hypergraphs have a subdivision drawing. However, this statement seems to be based on the assumption (also used in previous work) that the input hypergraph does not contain twins, pairs of vertices which are in precisely the same hyperedges (subsets of the universe). We show that such vertices may be necessary for a hypergraph to admit a subdivision drawing. As a counterpart, we show that the number of such “necessary twins” is upper-bounded by a function of the number m of hyperedges and a further parameter r of the desired drawing related to its number of layers. This leads to a linear-time algorithm for determining such subdivision drawings if m and r are constant; in other words, the problem is linear-time fixed-parameter tractable with respect to the parameters m and r.
BibTeX
@inproceedings{bevern2016twins,
  author = {René van Bevern and Iyad A. Kanj and Christian Komusiewicz and Rolf Niedermeier and Manuel Sorge},
  title = {{Twins in Subdivision Drawings of Hypergraphs}},
  booktitle = {GD},
  year = {2016},
  doi = {10.1007/978-3-319-50106-2\_6},
}
Figure