Generate elimination forests

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.

a b c d e f G d a c b e f T

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:

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.

Download source code

[Zipped C++ source code (GNU GPL)]

References