Laminar set family

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.

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]

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.