Generate all elimination forests of a chordal graph by tree rotations.
The graph is input as an edge list of the form $u_1,v_1; u_2,v_2; \ldots ; u_m,v_m$.
In such a list, edges are separated by semicolons, vertices are separated by commas, and whitespace is ignored.
The elimination forests in the output have their vertices labeled $1,2,\ldots,n$ according to a perfect elimination ordering that is computed initially.
Input graph
Predefined inputs
Output format
Output
numbering
graphics
Object info
An elimination tree of a connected graph $G$ is a rooted tree whose root is a vertex $v$ of $G$, and the subtrees of $v$ are obtained by recursing on the connected components of the graph obtained by removing $v$ from $G$.
The children of a vertex in an elimination tree are unordered.
An elimination forest of a graph $G$ (not necessarily connected) is the disjoint union of elimination trees, one for each connected component of $G$.
The figure below shows a graph $G$ on vertices $a,b,c,d,e,f$ (left) and one of its elimination trees $T$ (right), obtained by removing the vertices in the order $d,a,c,b,e,f$.
This graph can be used as input by selecting "example G" above.
There may be several elimination orders corresponding to the same elimination tree.
For example, removing the vertices in the order $d,f,a,c,e,b$ yields the same elimination tree.
Formally, the set of elimination orders corresponding to an elimination tree is the set of linear extensions of the poset whose Hasse diagram is the tree.
By choosing suitable families of graphs $G$, elimination forests encode many different combinatorial objects, and tree rotations in the elimination trees correspond to natural minimum change operations on those objects:
If $G$ is a path labeled $1,\ldots,n$ between its two end vertices, then its elimination trees correspond to binary trees. The distinction between left and right child of a vertex in an elimination tree is given by the smaller and larger labels. Elimination tree rotations correspond to classical rotations in binary trees.
If $G$ is a complete graph on $n$ vertices, then its elimination trees are paths, which can be interpreted as permutations, by reading off the vertices of the elimination tree from the root to the leaf of the path. Elimination tree rotations correspond to adjacent transpositions in the permutations.
If $G$ is a star with center $c$ and leaves $1,\ldots,n$, then its elimination trees are brooms, and reading off the vertices of the broom starting at the root and ending at the parent of $c$ yields partial permutations, i.e., linear orderings of all subsets of $\{1,\ldots,n\}$. Moreover, elimination tree rotations correspond to adjacent transpositions or deletions and insertions of a trailing element in a partial permutation.
If $G$ is a disjoint union of $n$ edges $\{i,n+i\}$, then its elimination forests correspond to bitstrings of length $n$, where the value of the $i$th bit is 0 if in the elimination forest the edge $\{i,n+i\}$ is rooted at $i$ and the bit is 1 if the edge is rooted at $n+i$. Elimination tree rotations correspond to flipping a single bit in the bitstrings.
If $G$ is a disjoint union of $n$ edges and a complete graph on $n$ vertices, then its elimination forest can be interpreted as signed permutations: The elimination tree of the complete graph determines the permutation, and the elimination trees for the edges determine the signs. Elimination tree rotations correspond to adjacent transpositions in the permutations (without changing the signs), or to sign reversals of a single entry in the permutation.
A graph $G$ is chordal if every induced cycle has length three.
Subclasses of chordal graphs include trees (in particular, paths and stars), complete graphs, $k$-trees, interval graphs, and split graphs.
In particular, they include the five classes of graphs mentioned before in the examples.
A perfect elimination ordering of a chordal graph is an ordering of the vertices such that each vertex forms a clique with the neighbors that appear before it in the ordering.
For example, a perfect elimination ordering of the graph $G$ shown in the figure above is $a,d,c,b,f,e$.
It was shown in [MP15] that if $G$ has at least two edges, then all its elimination forests can be ordered cyclically so that any two consecutive elimination forests differ in a single tree rotation.
These orderings of elimination forests correspond to Hamilton cycles on the skeleta of polytopes known as graph associahedra [CD06], [Pos09].
In the paper [CMM21] we propose an efficient algorithm for computing such an ordering for the case when $G$ is chordal (albeit the ordering is not necessarily cyclic).
The algorithm running on this website implements this algorithm, and it first outputs the perfect elimination ordering that is used for labeling the vertices of the input graph.
In the graphical output, the elimination trees are rotated to save space, with the root on the left and the tree growing to the right.
In the textual output, each elimination tree is traversed in DFS order, printing each vertex label followed by a sequence of dots corresponding to the number of children of that vertex in the elimination tree.
For example, the elimination tree shown above with the perfect elimination ordering $a,d,c,b,f,e$ is printed as 2.. 5 1. 3.. 4 6 (it appears at position 156 in the output for "example G")
Enumeration (OEIS)
The OEIS sequences listed below count the five combinatorial classes mentioned in the examples before.