Ordered Undirected Graphs

Why¹

Definition

An ordering of an undirected graph is an ordering (see Lists) of its vertices. An ordered undirected graph is a tuple: the first object is an undirected graph and the second object is an ordering of the graph.

Notation

Suppose $G = (V, E)$ is an undirected graph, $\sigma : \set{1, \dots , n} \to V$ is an ordering of $G$. Then $(G, \sigma )$ is an ordered undirected graph. Some authors associate the pair $(G, \sigma )$ with the triple $(V, E, \sigma )$ and call the latter an ordered undirected graph as well. Throughout these sheets we use the former structure.

We denote that $\inv{\sigma }(v) < \inv{\sigma }(w)$ by $v \prec_{\sigma } w$ and $v \succeq_{\sigma } w$ by $\inv{\sigma }(v) \leq \inv{\sigma }(w)$. We occasionally omit the subscripts in $\prec_{\sigma }$ and $\succeq_{\sigma }$ when clear from context.

Visualization

We visualize an ordered undirected graph by labeling its nodes with the indices of each vertex. Let $(V, E)$ be an undirected graph with $V = \set{a,b,c,d,e}$ and

\[ E = \set*{\set{a, b}, \set{a, c}, \set{a, e}, \set{b, d}, \set{b, e}, \set{c, d}, \set{c, e}, \set{d,e}}. \]

1. Future editions will include. This sheet is needed, for example, in discussing perfect elimination orderings. ↩︎