In graph theory, a bipolar orientation or st-orientation of an undirected graph is an assignment of a direction to each edge (an orientation) that causes the graph to become a directed acyclic graph with a single source s and a single sink t, and an st-numbering of the graph is a topological ordering of the resulting directed acyclic graph.
Definitions and existence
Let G = (V,E) be an undirected graph with n = |V| vertices. An orientation of G is an assignment of a direction to each edge of G, making it into a directed graph. It is an acyclic orientation if the resulting directed graph has no directed cycles. Every acyclically oriented graph has at least one source (a vertex with no incoming edges) and at least one sink (a vertex with no outgoing edges); it is a bipolar orientation if it has exactly one source and exactly one sink. In some situations, G may be given together with two designated vertices s and t; in this case, a bipolar orientation for s and t must have s as its unique source and t as its unique sink.
An st-numbering of G (again, with two designated vertices s and t) is an assignment of the integers from 1 to n to the vertices of G, such that each vertex is assigned a distinct number, s is assigned the number 1, t is assigned the number n, and if a vertex v is assigned the number i with 1 < i < n, then at least one neighbor of v is assigned a smaller number than i and at least one neighbor of v is assigned a larger number than i.
A graph has a bipolar orientation if and only if it has an st-numbering. For, if it has a bipolar orientation, then an st-numbering may be constructed by finding a topological ordering of the directed acyclic graph given by the orientation, and numbering each vertex by its position in the ordering. In the other direction, every st-numbering gives rise to a topological ordering, in which each edge of G is oriented from its lower-numbered endpoint to its higher-numbered endpoint. In a graph containing edge st, an orientation is bipolar if and only if it is acyclic and the orientation formed by reversing edge st is totally cyclic.
A connected graph G, with designated vertices s and t, has a bipolar orientation and an st-numbering if and only if the graph formed from G by adding an edge from s to t is 2-vertex-connected. In one direction, if this graph is 2-vertex-connected, then a bipolar orientation may be obtained by consistently orienting each ear in an ear decomposition of the graph. In the other direction, if the graph is not 2-vertex-connected, then it has an articulation vertex v separating some biconnected component of G from s and t. If this component contains a vertex with a lower number than v, then the lowest-numbered vertex in the component cannot have a lower-numbered neighbor, and symmetrically if it contains a vertex with a higher number than v then the highest-numbered vertex in the component cannot have a higher-numbered neighbor.
Applications to planarity
formulated st-numberings as part of a planarity testing algorithm, and formulated bipolar orientations as part of an algorithm for constructing tessellation representations of planar graphs.
A bipolar orientation of a planar graph results in an st-planar graph, a directed acyclic planar graph with one source and one sink. These graphs are of some importance in lattice theory as well as in graph drawing: the Hasse diagram of a two-dimensional lattice is necessarily st-planar, and every transitively reduced st-planar graph represents a two-dimensional lattice in this way. A directed acyclic graph G has an upward planar drawing if and only if G is a subgraph of an st-planar graph.