Laminar set family

All hyperedges here are either disjoint or related by containment. Edge 1 contains edge 4, and edges 3 and 5 contain each other. The set of hyperedges therefore forms a laminar set family.

In combinatorics, a laminar set family is a set family in which each pair of sets are either disjoint or related by containment. ^{[1] [2]}

Definition

Formally, a set family ${\displaystyle {\mathcal {F}}={S_{1},S_{2},\ldots }}$ is called laminar if for every ${\displaystyle i,j}$, the intersection ${\displaystyle S_{i}\cap S_{j}}$ is either empty, or equals ${\displaystyle S_{i}}$, or equals ${\displaystyle S_{j}}$.

Construction and Properties

Let ${\displaystyle E}$ be a ground-set of elements. A laminar set-family on ${\displaystyle E}$ can be constructed by recursively partitioning ${\displaystyle E}$ into parts and sub-parts. The singleton family ${\displaystyle {E}}$ is laminar. If we partition ${\displaystyle E}$ into some ${\displaystyle k}$ pairwise-disjoint parts ${\displaystyle E_{1},\ldots ,E_{k}}$, then ${\displaystyle {E,E_{1},\ldots ,E_{k}}}$ is laminar too. If we now partition, say ${\displaystyle E_{1}}$ into ${\displaystyle E_{11},E_{12},\ldots ,E_{1j}}$, then adding these sub-parts yields another laminar family, and so on. Hence, a laminar set-family can be seen as a hierarchical partitioning of the ground-set into categories and sub-categories.

A fundamental property of laminar set families is that they can be represented as a rooted tree where each node corresponds to a set in the family, and a set ${\displaystyle S_{i}}$ is an ancestor of ${\displaystyle S_{j}}$ if and only if ${\displaystyle S_{i}\supset S_{j}}$. This tree representation makes laminar families particularly useful in algorithm design, as many problems can be solved efficiently using dynamic programming on the tree structure.

Applications

Hypergraphs

The notion of laminarity can be applied to hypergraphs to define "laminar hypergraphs" as those whose set of hyperedges forms a laminar set family. ^[3]

Planar Graph Decomposition

Laminar families of separators play a crucial role in decomposing planar graphs. A k-separator (or k-cutset) in a k-connected graph is a subset of k vertices whose deletion disconnects the remaining graph. For planar graphs, the separators of small size often naturally form laminar families, which enables efficient algorithmic solutions.

Eppstein and Reed ^[4] showed that for a 3-connected planar graph ${\displaystyle G}$, a maximal set of laminar 3-separators can be found in linear time. This is non-trivial because some planar graphs like wheel graphs can have ${\displaystyle \Theta (n^{2})}$ 3-separators and ${\displaystyle \Theta (n^{4})}$ non-laminar pairs of 3-separators, making it inefficient to enumerate all separators and then select a laminar subset.

Their algorithm works by transforming the problem: 3-separators in the original graph ${\displaystyle G}$ correspond to certain 6-cycles in the barycentric subdivision ${\displaystyle {\text{BCS}}(G)}$. The algorithm identifies "frames" (wheel-like structures containing many mutually non-laminar cycles) and handles them separately to avoid quadratic blow-up in complexity. This decomposition has important applications in finding disjoint paths in graphs and computing tree decompositions of bounded adhesion.

Beginning with the work of Wagner, ^[5] decompositions of graphs by laminar sets of small cutsets have been an important tool in graph structure theory. Wagner showed that every ${\displaystyle K_{5}}$-minor-free graph can be decomposed by a laminar system of cutsets of size at most three into pieces that are either planar or the eight-vertex Wagner graph. Many similar decomposition theorems are now known, and tree decompositions and treewidth are also defined by laminar cutsets.

References

1. Cheriyan, Joseph; Jordán, Tibor; Ravi, R. (1999). "On 2-Coverings and 2-Packings of Laminar Families". In Nešetřil, Jaroslav (ed.). Algorithms - ESA' 99. Lecture Notes in Computer Science. Vol. 1643. Berlin, Heidelberg: Springer. pp. 510–520. doi:10.1007/3-540-48481-7_44. ISBN   978-3-540-48481-3.
2. Maduel, Yael; Nutov, Zeev (2010-07-06). "Covering a laminar family by leaf to leaf links". Discrete Applied Mathematics. 158 (13): 1424–1432. doi: 10.1016/j.dam.2010.04.002 . ISSN   0166-218X.
3. Rautenbach, Dieter; Szigeti, Zoltán (2012-08-01). "Greedy colorings of words". Discrete Applied Mathematics. 160 (12): 1872–1874. doi: 10.1016/j.dam.2012.03.038 . ISSN   0166-218X.
4. Eppstein, David; Reed, Bruce (2019). "Finding Maximal Sets of Laminar 3-Separators in Planar Graphs in Linear Time". Proceedings of the 2019 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). pp. 589–605. doi:10.1137/1.9781611975482.37.
5. Wagner, K. (1937). "Über eine Eigenschaft der ebenen Komplexe" [On a Property of Planar Complexes]. Mathematische Annalen (in German). 114: 570–590. doi:10.1007/BF01594196. ISSN   0025-5831.