Introduction

An st-ordering (or bipolar odering) of a simple undirected graph is $G = (V, E)$ is a specific permutation $l$ of vertices, where any permutation $l$ induces a natural partial order on vertices $u < v \iff l(u) < l(v) \text{ and } uv \in E$. $l$ is called to be an st-ordering if and only if for a given pair of vertices $(s, t)$, $s$ (resp. $t$) is the unique minimal (resp. maximal) element w.r.t $<$.

Here, we discuss the existence condition of an st-ordering and the linear-time algorithm to find it if exists.

Existence condition

Theorem 1. $G$ has an $st$-ordering if and only if $G + st$ is 2-vertex connected.

Proof. We will constructively proof the existence with the provided condition, so we discuss the negative case. Assume contradictory – $G$ has an $st$-ordering $l$ even if $G + st$ is not 2-vertex connected. Assume a cut vertex $v$ that separates another component $C$ from $\set{s, t}$. Let $a, b \in C$ be the vertices with the minimum / maximum label, respectively.

As both $a, b$ is neither $s$ nor $t$, both must have neighbors with smaller and larger label compared to itself, and one can easily show the impossibility. $\square$

Linear-time algorithm

It is known that the $st$-ordering is a result that can be derived almost trivially from chain decomposition (Schmidt, 2013), a specific type of ear decomposition. However, we will delve into a more concrete algorithm. The correspondence with the algorithm provided by Schmidt13 is not entirely clear in my knowledge.

I wrote the document in reference to this submission and following discussions of friends.

Subroutine - Biconnected graph with prescribed source

As a (nearly complete) subroutine, we will design an algorithm to establish an ordering $l$ for a 2-vertex connected graph $G$ with a given source $s$. This ordering will ensure that $s$ serves as the unique minimal element, and there exists a unique maximal element. For simplicity, we assume the presence of at least 2 distinct vertices.

To begin, we introduce the Depth-First Search (DFS) tree $T$ rooted at $s$. In this context, we define the “low-link” $\mr{low}(v)$ for a vertex $v$ as the highest depth reachable from the subtree of $v$ by utilizing a single back-edge. It’s important to note that for any vertex $v \neq s$, $\mr{low}(v) \le \mr{depth}(p_{v})$, where $p_{v}$ represents the parent vertex of $v$. This property holds true due to the 2-vertex connectivity of $G$.

We will transform $T$ into a search tree and designate $l$ as the result of an in-order traversal of $T$. To achieve this, we must establish “directions” (left/right) for each subtree attached to every vertex. And then $l$ will naturally encode the subtree rooted on $v$ into $(\text{Left subtrees from }v),v,(\text{Right subtrees from }v)$. Relative orders between subtrees with the same direction doesn’t matter.

  • For $s$, we will put all the subtrees in right. This will ensure that $s$ is with the minimum label.
  • For any $v \neq s$, we’ll propagate the direction based on its ancestors'.
    • For a vertex $v$ given the direction from $p_{v}$ and its child $w$ (i.e. $p_{w} = v$)
      • If $\mr{low}(w) < \mr{depth}(v)$, direction of $w$ w.r.t $v$ is opposite of the direction of $v$ w.r.t. $\mr{low}(w)$.
      • Otherwise, $\mr{low}(w) = \mr{depth}(v)$ must hold. Actually this concludes that $v$ is the root, otherwise we can prove that $v$ is an articulation point. So we already know how to orient $w$.

Note that $s$ will bear the only child vertex $c$. This child will be the maximal element, and the other vertices will be located between two. We prove that all vertices $v \notin \set{s, c}$ is neither minimal nor maximal w.r.t. the induced partial order.

  • If $\mr{low}(v) < \mr{low}(w)$ for any child $w$, it is in between its parent and its low-link – the vertex who gives $\mr{low}(v)$.
  • If $\mr{low}(v) = \mr{low}(w)$ for some child $w$, $v$ is in between $w$ and $p_{v}$, we know that $\mr{low}(v) < \mr{depth}(p_{v})$. Thus $v$ should be oriented w.r.t $p_{v}$ just as $w$ is oriented w.r.t $v$. $\square$

Completion

Given the subroutine, we can complete the $st$-ordering by putting $st \in E$ to be the only tree edge from $s$. $\square$

References

  • Wikipedia contributors. “Bipolar orientation.” Wikipedia, The Free Encyclopedia. Wikipedia, The Free Encyclopedia, 18 Aug. 2023. Web. 1 Jan. 2024.
  • Schmidt, Jens M. “A simple test on 2-vertex-and 2-edge-connectivity.” Information Processing Letters 113.7 (2013): 241-244.