graph theory In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, a bipolar orientation or ''st''-orientation of an

undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...

is an assignment of a direction to each edge (an

orientation Orientation may refer to: Positioning in physical space * Map orientation, the relationship between directions on a map and compass directions * Orientation (housing), the position of a building with respect to the sun, a concept in building desi ...

) that causes the graph to become a

directed acyclic graph In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called ''arcs''), with each edge directed from one v ...

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

of ''G'' is an assignment of a direction to each edge of ''G'', making it into a

directed graph In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs. Definition In formal terms, a directed graph is an ordered pai ...

. It is an acyclic orientation if the resulting directed graph has no

directed cycle Director may refer to: Literature * ''Director'' (magazine), a British magazine * ''The Director'' (novel), a 1971 novel by Henry Denker * ''The Director'' (play), a 2000 play by Nancy Hasty Music * Director (band), an Irish rock band * ''D ...

s. 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 In graph theory, the planarity testing problem is the algorithmic problem of testing whether a given graph is a planar graph (that is, whether it can be drawn in the plane without edge intersections). This is a well-studied problem in computer scie ...

algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...

, and formulated bipolar orientations as part of an algorithm for constructing tessellation representations of

planar graph In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cro ...

s. 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 A lattice is an abstract structure studied in the mathematical subdisciplines of order theory and abstract algebra. It consists of a partially ordered set in which every pair of elements has a unique supremum (also called a least upper bou ...

as well as in

graph drawing Graph drawing is an area of mathematics and computer science combining methods from geometric graph theory and information visualization to derive two-dimensional depictions of graphs arising from applications such as social network analysis, car ...

: the

Hasse diagram In order theory, a Hasse diagram (; ) is a type of mathematical diagram used to represent a finite partially ordered set, in the form of a drawing of its transitive reduction. Concretely, for a partially ordered set ''(S, ≤)'' one represents ...

of a

two-dimensional In mathematics, a plane is a Euclidean ( flat), two-dimensional surface that extends indefinitely. A plane is the two-dimensional analogue of a point (zero dimensions), a line (one dimension) and three-dimensional space. Planes can arise ...

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 In graph drawing, an upward planar drawing of a directed acyclic graph is an embedding of the graph into the Euclidean plane, in which the edges are represented as non-crossing monotonic upwards curves. That is, the curve representing each ed ...

if and only if ''G'' is a subgraph of an ''st''-planar graph.

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 In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by t ...

using

depth-first search Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible alo ...

. The algorithm of 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 In mathematics, especially in order theory, a preorder or quasiorder is a binary relation that is reflexive and transitive. Preorders are more general than equivalence relations and (non-strict) partial orders, both of which are special c ...

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

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 In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes whi ...

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. Alternatively, efficient sequential and parallel algorithms may be based on ear decomposition. 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, or by more direct methods. 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. A modern and simple algorithm that computes ''st''-numberings and -orientations in linear time is given in. 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. 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

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. 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 In mathematics, especially order theory, the covering relation of a partially ordered set is the binary relation which holds between comparable elements that are immediate neighbours. The covering relation is commonly used to graphically expr ...

of the lattice. For any graph with designated source and sink, the set of all bipolar orientations may be listed in polynomial time per orientation.

''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 In the mathematical discipline of graph theory, the line graph of an undirected graph is another graph that represents the adjacencies between edges of . is constructed in the following way: for each edge in , make a vertex in ; for every ...

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.

References

{{reflist, 30em, refs= {{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 Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory. It is difficult to circumsc ...

, pages = 175–198 , title = Algorithms for plane representations of acyclic digraphs , volume = 61 , year = 1988, doi-access = free . {{citation , last = Ebert , first = J. , doi = 10.1007/BF02253293 , issue = 1 , journal =

Computing Computing is any goal-oriented activity requiring, benefiting from, or creating computing machinery. It includes the study and experimentation of algorithmic processes, and development of both hardware and software. Computing has scientific, ...

, mr = 691948 , pages = 19–33 , title = ''st''-ordering the vertices of biconnected graphs , volume = 30 , year = 1983. {{citation , last1 = Even , first1 = Shimon , author1-link = Shimon Even , last2 = Tarjan , first2 = Robert Endre , author2-link = Robert Tarjan , issue = 3 , journal =

, mr = 0414406 , pages = 339–344 , title = Computing an ''st''-numbering , volume = 2 , year = 1976 , doi=10.1016/0304-3975(76)90086-4, doi-access = free . {{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 . {{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. {{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. {{citation , last1 = Maon , first1 = Y. , last2 = Schieber , first2 = B. , last3 = Vishkin , first3 = U. , author3-link = Uzi Vishkin , journal =

, 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 . {{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 , contribution-url = http://www.cs.berkeley.edu/~cpap/published/cpap-igt-05.pdf , volume = 3843 , year = 2006, doi-access = free . {{citation , last = Platt , first = C. R. , doi = 10.1016/0095-8956(76)90024-1 , issue = 1 , journal =

Journal of Combinatorial Theory The ''Journal of Combinatorial Theory'', Series A and Series B, are mathematical journals specializing in combinatorics and related areas. They are published by Elsevier. ''Series A'' is concerned primarily with structures, designs, and applicat ...

, series = Ser. B , pages = 30–39 , title = Planar lattices and planar graphs , volume = 21 , year = 1976, doi-access = free . {{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 '' Discrete & Computational Geometry'' is a peer-reviewed mathematics journal published quarterly by Springer. Founded in 1986 by Jacob E. Goodman and Richard M. Pollack, the journal publishes articles on discrete geometry and computational ge ...

, mr = 866369 , pages = 343–353 , title = Rectilinear planar layouts and bipolar orientations of planar graphs , volume = 1 , year = 1986, doi-access = free . {{citation , last1 = Schlipf , first1 = Lena , last2 = Schmidt , first2 = Jens M. , doi = 10.1016/j.ipl.2019.01.008 , journal =

Information Processing Letters ''Information Processing Letters'' is a peer reviewed scientific journal in the field of computer science, published by Elsevier. The aim of the journal is to enable fast dissemination of results in the field of information processing Information ...

, pages = 58–63 , title = Simple computation of st-edge- and st-numberings from ear decompositions , volume = 145 , year = 2019. {{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 . Graph theory objects

Definitions and existence

Applications to planarity

Algorithms

The space of all orientations

''st''-edge-numberings and -orientations

See also

References