{{Short description|Graph orientation with one source and sink}} thumb|upright=1.35|A bipolar orientation and ''st''-numbering (right) of an undirected graph (left). A single source and sink are established, and all edges are directed from the former to the latter. Vertices are numbered such that the numbers increase along any path.
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.<ref name="rt86"/><ref name="fmt95"/>
==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.<ref name="rt86"/><ref name="fmt95"/>
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''.<ref name="rt86"/><ref name="fmt95"/><ref name="lec66"/>
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.<ref name="rt86"/><ref name="fmt95"/> 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.<ref name="fmt95"/>
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.<ref name="lec66"/> 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.<ref name="msv86"/> 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== {{harvtxt|Lempel|Even|Cederbaum|1967}} formulated ''st''-numberings as part of a planarity testing algorithm,<ref name="lec66"/> and {{harvtxt|Rosenstiehl|Tarjan|1986}} formulated bipolar orientations as part of an algorithm for constructing tessellation representations of planar graphs.<ref name="rt86"/>
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.<ref name="platt76"/> A directed acyclic graph ''G'' has an upward planar drawing if and only if ''G'' is a subgraph of an ''st''-planar graph.<ref name="dbt88"/>
==Algorithms== 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.<ref name="ebert83"/><ref name="et76"/><ref name="t86"/> The algorithm of {{harvtxt|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. Both of these numbers may be computed in linear time as part of the depth-first search. 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. Initially, the list contains ''s'' and ''t'', and sign(''s'') = −1. When each vertex ''v'' is first encountered by this second traversal, ''v'' is inserted into the list, either before or after its parent p(''v'') in the depth-first search tree according to whether sign(low(''v'')) is negative or positive respectively; then sign(p(''v'')) is set to −sign(low(''v'')). As Tarjan shows, the vertex ordering resulting from this procedure gives an ''st''-numbering of the given graph.<ref name="t86"/>
Alternatively, efficient sequential and parallel algorithms may be based on ear decomposition.<ref name="msv86"/><ref name="g91"/><ref name="ss19"/> While the DFS-based algorithms above depend inherently on the special open ear decomposition caused by the underlying DFS-tree, the open ear decomposition here may be arbitrary. This more general approach is actually used by several applications, e.g. for computing (edge-)independent spanning trees. An open ear decomposition exists if and only if the graph formed from the given graph by adding an edge ''st'' is biconnected (the same condition as the existence of a bipolar orientation), and it can be found in linear time. An ''st''-orientation (and thus also an ''st''-numbering) may be obtained easily by directing each ear in a consistent direction, taking care that if there already exists a directed path connecting the same two endpoints among the edges of previous ears then the new ear must be oriented in the same direction. However, despite the simplicity of this folklore approach, obtaining a linear running time is more involved. Whenever an ear is added, the endpoints of this ear must be checked on reachability, or, equivalently for the ''st''-numbering, which vertex comes first in the preliminary ''st''-numbering before. This obstacle can be solved in worst-case constant time by using the (somewhat involved) order data structure,<ref name="ss19"/> or by more direct methods. {{harvtxt|Maon|Schieber|Vishkin|1986}} provide a complicated but localized search procedure for determining an appropriate orientation for each ear that (unlike the approach using depth-first search) is suitable for parallel computation.<ref name="msv86"/>
A modern and simple algorithm that computes ''st''-numberings and -orientations in linear time is given in.<ref name="ss19"/> 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.
{{harvtxt|Papamanthou|Tollis|2006}} report on algorithms for controlling the lengths of the directed paths in a bipolar orientation of a given graph, which in turn leads to some control over the width and height of certain types of graph drawing.<ref name="pt05"/>
==The space of all orientations== For 3-vertex-connected graphs, with designated vertices ''s'' and ''t'', any two bipolar orientations may be connected to each other by a sequence of operations that reverse one edge at a time, at each step maintaining a bipolar orientation.<ref name="fmt95"/> More strongly, for planar 3-connected graphs, the set of bipolar orientations can be given the structure of a finite distributive lattice, with the edge-reversal operation corresponding to the covering relation of the lattice.<ref name="fmt95"/> For any graph with designated source and sink, the set of all bipolar orientations may be listed in polynomial time per orientation.<ref name="fmt95"/>
==''st''-edge-numberings and -orientations==
One may construct an ordering that is similar to ''st''-numberings by numbering edges instead of vertices. This is equivalent to ''st''-numbering the line graph of the input graph. 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.<ref name="ss19"/>
==See also== *Convex embedding, a higher-dimensional generalization of bipolar orientations
==References== {{reflist|30em|refs= <ref name="dbt88">{{citation | last1 = Di Battista | first1 = Giuseppe | last2 = Tamassia | first2 = Roberto | doi = 10.1016/0304-3975(88)90123-5 | issue = 2–3 | journal = Theoretical Computer Science | pages = 175–198 | title = Algorithms for plane representations of acyclic digraphs | volume = 61 | year = 1988| doi-access = }}.</ref> <ref name="ebert83">{{citation | last = Ebert | first = J. | doi = 10.1007/BF02253293 | issue = 1 | journal = Computing | mr = 691948 | pages = 19–33 | title = ''st''-ordering the vertices of biconnected graphs | volume = 30 | year = 1983| s2cid = 6570953 }}.</ref> <ref name="et76">{{citation | last1 = Even | first1 = Shimon | author1-link = Shimon Even | last2 = Tarjan | first2 = Robert Endre | author2-link = Robert Tarjan | issue = 3 | journal = Theoretical Computer Science | mr = 0414406 | pages = 339–344 | title = Computing an ''st''-numbering | volume = 2 | year = 1976 | doi=10.1016/0304-3975(76)90086-4| doi-access = }}.</ref> <ref name="fmt95">{{citation | last1 = de Fraysseix | first1 = Hubert | last2 = Ossona de Mendez | first2 = Patrice | author2-link = Patrice Ossona de Mendez | last3 = Rosenstiehl | first3 = Pierre | author3-link = Rosenstiehl | doi = 10.1016/0166-218X(94)00085-R | issue = 2–3 | journal = Discrete Applied Mathematics | mr = 1318743 | pages = 157–179 | title = Bipolar orientations revisited | volume = 56 | year = 1995| doi-access = free }}.</ref> <ref name="g91">{{citation | last = Gazit | first = Hillel | contribution = Optimal EREW parallel algorithms for connectivity, ear decomposition and st-numbering of planar graphs | doi = 10.1109/IPPS.1991.153761 | pages = 84–91 | title = Proc. 5th International Parallel Processing Symposium | year = 1991| isbn = 0-8186-9167-0 | s2cid = 34959564 }}.</ref> <ref name="lec66">{{citation | last1 = Lempel | first1 = A. | author1-link = Abraham Lempel | last2 = Even | first2 = S. | author2-link = Shimon Even | last3 = Cederbaum | first3 = I. | contribution = An algorithm for planarity testing of graphs | location = New York | mr = 0220617 | pages = 215–232 | publisher = Gordon and Breach | title = Theory of Graphs (Internat. Sympos., Rome, 1966) | year = 1967}}.</ref> <ref name="msv86">{{citation | last1 = Maon | first1 = Y. | last2 = Schieber | first2 = B. | last3 = Vishkin | first3 = U. | author3-link = Uzi Vishkin | journal = Theoretical Computer Science | title = Parallel ear decomposition search (EDS) and ST-numbering in graphs | volume = 47 | issue = 3 | mr = 0882357 | doi = 10.1016/0304-3975(86)90153-2 | year = 1986| pages = 277–298 | doi-access = free }}.</ref> <ref name="pt05">{{citation | last1 = Papamanthou | first1 = Charalampos | last2 = Tollis | first2 = Ioannis G. | contribution = Applications of parameterized ''st''-orientations in graph drawing algorithms | doi = 10.1007/11618058_32 | location = Berlin | mr = 2244524 | pages = 355–367 | publisher = Springer | series = Lecture Notes in Computer Science | title = Graph Drawing: 13th International Symposium, GD 2005, Limerick, Ireland, September 12–14, 2005, Revised Papers | volume = 3843 | year = 2006 | doi-access = free | isbn = 978-3-540-31425-7 }}</ref> <ref name="platt76">{{citation | last = Platt | first = C. R. | doi = 10.1016/0095-8956(76)90024-1 | issue = 1 | journal = Journal of Combinatorial Theory | series = Ser. B | pages = 30–39 | title = Planar lattices and planar graphs | volume = 21 | year = 1976| doi-access = }}.</ref> <ref name="rt86">{{citation | last1 = Rosenstiehl | first1 = Pierre | author1-link = Pierre Rosenstiehl | last2 = Tarjan | first2 = Robert E. | author2-link = Robert Tarjan | doi = 10.1007/BF02187706 | issue = 4 | journal = Discrete and Computational Geometry | mr = 866369 | pages = 343–353 | title = Rectilinear planar layouts and bipolar orientations of planar graphs | volume = 1 | year = 1986| doi-access = free }}.</ref> <ref name="ss19">{{citation | last1 = Schlipf | first1 = Lena | last2 = Schmidt | first2 = Jens M. | doi = 10.1016/j.ipl.2019.01.008 | journal = Information Processing Letters | pages = 58–63 | title = Simple computation of st-edge- and st-numberings from ear decompositions | volume = 145 | year = 2019| s2cid = 71714734 }}.</ref> <ref name="t86">{{citation | last = Tarjan | first = Robert Endre | authorlink = Robert Tarjan | issue = 1 | journal = Fundamenta Informaticae | mr = 848212 | pages = 85–94 | title = Two streamlined depth-first search algorithms | url = http://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/two_stremlined.pdf | volume = 9 | year = 1986| doi = 10.3233/FI-1986-9105 }}.</ref> }}
Category:Graph theory objects