Bipolar orientation

Lempel, Even & Cederbaum (1967) formulated st-numberings as part of a planarity testing algorithm,[3] and Rosenstiehl & Tarjan (1986) formulated bipolar orientations as part of an algorithm for constructing tessellation representations of planar graphs.

[6] It is possible to find an st-numbering, and a bipolar orientation, of a given graph with designated vertices s and t, in linear time using depth-first search.

[7][8][9] The algorithm of Tarjan (1986) uses a depth-first search that starts at vertex s and first traverses edge st. As in the depth-first-search based algorithm for testing whether a graph is biconnected, this algorithm defines pre(v), for a vertex v, to be the preorder number of v in the depth-first traversal, and low(v) to be the smallest preorder number that can be reached by following a single edge from a descendant of v in the depth-first search tree.

The given graph will be biconnected (and will have a bipolar orientation) if and only if t is the only child of s in the depth-first search tree and low(v) < pre(v) for all vertices v other than s. Once these numbers have been computed, Tarjan's algorithm performs a second traversal of the depth-first search tree, maintaining a number sign(v) for each vertex v and a linked list of vertices that will eventually list all vertices of the graph in the order given by an st-numbering.

As Tarjan shows, the vertex ordering resulting from this procedure gives an st-numbering of the given graph.

This obstacle can be solved in worst-case constant time by using the (somewhat involved) order data structure,[11] or by more direct methods.

[11] The idea of this algorithm is to replace the order data structure by an easy numbering scheme, in which vertices carry intervals instead of st-numbers.

Although constructing the line-graph explicitly would take quadratic time, linear-time algorithms for computing an st-edge-numbering and st-edge-orientation of a graph are known.