The Combinatorial Object Server

Input (hyper)graph | |

Predefined inputs | |

Output format | |

Output
numbering
graphics

An orientation of an undirected graph $G=(V,E)$ is the directed graph obtained by replacing every undirected edge from $E$ with an arc in one of the two possible directions.
Such an orientation is acyclic if it does not have directed cycles.
More generally, an orientation of a hypergraph $H=(V,E)$, where $E\subseteq 2^V$, is a mapping $h:E\rightarrow V$ such that $h(X)\in X$ for all $X\in E$.
We refer to $h(X)$ as the head of the hyperedge $X$.
Such an orientation is acyclic if the directed graph $G_h=(V,A)$ with $A:=\{v\rightarrow h(X)\mid v\in X\in E\text{ and } v\neq h(X)\}$ is acyclic.
Information on chordal graphs, in particular the notion of perfect elimination order, can be found on the elimination tree page.

The figure shows an acyclic orientation of a diamond graph. This graph can be used as input by selecting "example G" above. In the output generated by the website, the orientation of each (hyper)edge is specified by highlighting the head by square brackets [ ]. For example, the orientation of the diamond shown above in the perfect elimination order $b,a,c,d$ is printed as [1],2; [2],4; 2,[3]; [1],3; [3],4 (it appears at position 15 in the output for "example G")

The algorithm for acyclic orientations of chordal graphs was discovered by Savage, Squire and West [SSW93], and an efficient implementation was described in [CHM+23]. The more general algorithm for acyclic orientation of hypergraphs in hyperfect elimination order was also described in [CHM+23]. See this paper for the definition of hyperfect elimination order.

Many combinatorial objects can be encoded as acyclic orientations of graphs and hypergraphs. In particular, elimination trees of a graph $G$ (and all the different combinatorial objects they encode) can be captured by considering as hyperedges all connected subsets of vertices of $G$; this is the so-called graphical building set of $G$.

- [CHM+23] J. Cardinal, H. P. Hoang, A. Merino, O. Mička, and T. Mütze. Combinatorial generation via permutation languages. V. Acyclic orientations. SIAM J. Discrete Math., 37(3):1509–1547, 2023.
- [SSW93] C. D. Savage, M. B. Squire, and D. B. West. Gray code results for acyclic orientations. In Proceedings of the Twenty-fourth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1993), volume 96, pages 185–204, 1993.