Ordered Undirected Graph Orientations

Why

There is a natural orientation of an ordered undirected graph.

Motivating result

An ordered undirected graph can be converted into a directed graph by orienting the edges from lower to higher index. The orientation of an ordered undirected graph $((V, E),\sigma )$ is the directed graph $(V, F)$ where

\[ \set{v, w} \in V \implies (v, w) \in F \text{ and } \inv{\sigma }(v) < \inv{\sigma }(w). \]

In other words, we can “convert” the ordered undirected graph by “orienting” the edges from lower to higher index.

Let $G = ((V, E), \sigma )$ be an ordered undirected graph. The orientation of $G$ is acyclic.

Contradiction on the existence of a cycle.¹

Conversely, let $(V, F)$ be directed acyclic. To each topological numbering $\sigma $ of $(V, F)$ (see Directed Paths) there exists an ordered undirected graph $((V, E), \sigma )$ where $(V, E)$ is the skeleton of $(V, F)$.

Example

Let $G = ((V, E), \sigma )$ be an undirected graph with

\[ V = \set{a,b,c,d,e}, \]

\[ 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}}, \]

and

\[ \sigma (1) = a \quad \sigma (2) = c \quad \sigma (3) = d \quad \sigma (4) = b \quad \sigma (e) = 5. \]

We visualize $G$ and its (directed acyclic) orientation above.

Future editions will expand. ↩︎