Bipolar orientation

Last updated

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. [1] [2]

Contents

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. [1] [2]

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

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. [1] [2] 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. [2]

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. [3] 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. [4] 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

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. [1]

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. [5] A directed acyclic graph G has an upward planar drawing if and only if G is a subgraph of an st-planar graph. [6]

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. [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. 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. [9]

Alternatively, efficient sequential and parallel algorithms may be based on ear decomposition. [4] [10] [11] 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, [11] or by more direct methods. 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. [4]

A modern and simple algorithm that computes st-numberings and -orientations in linear time is given in. [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.

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. [12]

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. [2] 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. [2] For any graph with designated source and sink, the set of all bipolar orientations may be listed in polynomial time per orientation. [2]

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. [11]

See also

Related Research Articles

<span class="mw-page-title-main">Depth-first search</span> Search algorithm

Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node and explores as far as possible along each branch before backtracking. Extra memory, usually a stack, is needed to keep track of the nodes discovered so far along a specified branch which helps in backtracking of the graph.

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

<span class="mw-page-title-main">Strongly connected component</span> Partition of a graph whose components are reachable from all vertices

In the mathematical theory of directed graphs, a graph is said to be strongly connected if every vertex is reachable from every other vertex. The strongly connected components of an arbitrary directed graph form a partition into subgraphs that are themselves strongly connected. It is possible to test the strong connectivity of a graph, or to find its strongly connected components, in linear time (that is, Θ(V + E)).

<span class="mw-page-title-main">Chordal graph</span> Graph where all long cycles have a chord

In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced cycle in the graph should have exactly three vertices. The chordal graphs may also be characterized as the graphs that have perfect elimination orderings, as the graphs in which each minimal separator is a clique, and as the intersection graphs of subtrees of a tree. They are sometimes also called rigid circuit graphs or triangulated graphs.

<span class="mw-page-title-main">Bridge (graph theory)</span> Edge in node-link graph whose removal would disconnect the graph

In graph theory, a bridge, isthmus, cut-edge, or cut arc is an edge of a graph whose deletion increases the graph's number of connected components. Equivalently, an edge is a bridge if and only if it is not contained in any cycle. For a connected graph, a bridge can uniquely determine a cut. A graph is said to be bridgeless or isthmus-free if it contains no bridges.

<span class="mw-page-title-main">Circuit rank</span> Fewest graph edges whose removal breaks all cycles

In graph theory, a branch of mathematics, the circuit rank, cyclomatic number, cycle rank, or nullity of an undirected graph is the minimum number of edges that must be removed from the graph to break all its cycles, making it into a tree or forest. It is equal to the number of independent cycles in the graph. Unlike the corresponding feedback arc set problem for directed graphs, the circuit rank r is easily computed using the formula

<span class="mw-page-title-main">Dual graph</span> Graph representing faces of another graph

In the mathematical discipline of graph theory, the dual graph of a planar graph G is a graph that has a vertex for each face of G. The dual graph has an edge for each pair of faces in G that are separated from each other by an edge, and a self-loop when the same face appears on both sides of an edge. Thus, each edge e of G has a corresponding dual edge, whose endpoints are the dual vertices corresponding to the faces on either side of e. The definition of the dual depends on the choice of embedding of the graph G, so it is a property of plane graphs rather than planar graphs. For planar graphs generally, there may be multiple dual graphs, depending on the choice of planar embedding of the graph.

<span class="mw-page-title-main">Biconnected component</span> Maximal biconnected subgraph

In graph theory, a biconnected component is a maximal biconnected subgraph. Any connected graph decomposes into a tree of biconnected components called the block-cut tree of the graph. The blocks are attached to each other at shared vertices called cut vertices or separating vertices or articulation points. Specifically, a cut vertex is any vertex whose removal increases the number of connected components.

<span class="mw-page-title-main">SPQR tree</span> Representation of a graphs triconnected components

In graph theory, a branch of mathematics, the triconnected components of a biconnected graph are a system of smaller graphs that describe all of the 2-vertex cuts in the graph. An SPQR tree is a tree data structure used in computer science, and more specifically graph algorithms, to represent the triconnected components of a graph. The SPQR tree of a graph may be constructed in linear time and has several applications in dynamic graph algorithms and graph drawing.

In graph theory, the strongly connected components of a directed graph may be found using an algorithm that uses depth-first search in combination with two stacks, one to keep track of the vertices in the current component and the second to keep track of the current search path. Versions of this algorithm have been proposed by Purdom (1970), Munro (1971), Dijkstra (1976), Cheriyan & Mehlhorn (1996), and Gabow (2000); of these, Dijkstra's version was the first to achieve linear time.

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 science for which many practical algorithms have emerged, many taking advantage of novel data structures. Most of these methods operate in O(n) time (linear time), where n is the number of edges (or vertices) in the graph, which is asymptotically optimal. Rather than just being a single Boolean value, the output of a planarity testing algorithm may be a planar graph embedding, if the graph is planar, or an obstacle to planarity such as a Kuratowski subgraph if it is not.

In graph theory, a strong orientation of an undirected graph is an assignment of a direction to each edge that makes it into a strongly connected graph.

In graph theory, the planar separator theorem is a form of isoperimetric inequality for planar graphs, that states that any planar graph can be split into smaller pieces by removing a small number of vertices. Specifically, the removal of vertices from an n-vertex graph can partition the graph into disjoint subgraphs each of which has at most vertices.

<span class="mw-page-title-main">Degeneracy (graph theory)</span> Measurement of graph sparsity

In graph theory, a k-degenerate graph is an undirected graph in which every subgraph has a vertex of degree at most k: that is, some vertex in the subgraph touches k or fewer of the subgraph's edges. The degeneracy of a graph is the smallest value of k for which it is k-degenerate. The degeneracy of a graph is a measure of how sparse it is, and is within a constant factor of other sparsity measures such as the arboricity of a graph.

In graph theory, a Trémaux tree of an undirected graph is a type of spanning tree, generalizing depth-first search trees. They are defined by the property that every edge of connects an ancestor–descendant pair in the tree. Trémaux trees are named after Charles Pierre Trémaux, a 19th-century French author who used a form of depth-first search as a strategy for solving mazes. They have also been called normal spanning trees, especially in the context of infinite graphs.

<span class="mw-page-title-main">Ear decomposition</span> Partition of graph into sequence of paths

In graph theory, an ear of an undirected graph G is a path P where the two endpoints of the path may coincide, but where otherwise no repetition of edges or vertices is allowed, so every internal vertex of P has degree two in G. An ear decomposition of an undirected graph G is a partition of its set of edges into a sequence of ears, such that the one or two endpoints of each ear belong to earlier ears in the sequence and such that the internal vertices of each ear do not belong to any earlier ear. Additionally, in most cases the first ear in the sequence must be a cycle. An open ear decomposition or a proper ear decomposition is an ear decomposition in which the two endpoints of each ear after the first are distinct from each other.

In graph theory, an orientation of an undirected graph is an assignment of a direction to each edge, turning the initial graph into a directed graph.

<span class="mw-page-title-main">Acyclic orientation</span>

In graph theory, an acyclic orientation of an undirected graph is an assignment of a direction to each edge that does not form any directed cycle and therefore makes it into a directed acyclic graph. Every graph has an acyclic orientation.

<span class="mw-page-title-main">Upward planar drawing</span> Graph with edges non-crossing and upward

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 edge should have the property that every horizontal line intersects it in at most one point, and no two edges may intersect except at a shared endpoint. In this sense, it is the ideal case for layered graph drawing, a style of graph drawing in which edges are monotonic curves that may cross, but in which crossings are to be minimized.

In graph theory, an st-planar graph is a bipolar orientation of a plane graph for which both the source and the sink of the orientation are on the outer face of the graph. That is, it is a directed graph drawn without crossings in the plane, in such a way that there are no directed cycles in the graph, exactly one graph vertex has no incoming edges, exactly one graph vertex has no outgoing edges, and these two special vertices both lie on the outer face of the graph.

References

  1. 1 2 3 4 5 Rosenstiehl, Pierre; Tarjan, Robert E. (1986), "Rectilinear planar layouts and bipolar orientations of planar graphs", Discrete and Computational Geometry , 1 (4): 343–353, doi: 10.1007/BF02187706 , MR   0866369 .
  2. 1 2 3 4 5 6 7 8 de Fraysseix, Hubert; Ossona de Mendez, Patrice; Rosenstiehl, Pierre (1995), "Bipolar orientations revisited", Discrete Applied Mathematics, 56 (2–3): 157–179, doi: 10.1016/0166-218X(94)00085-R , MR   1318743 .
  3. 1 2 3 Lempel, A.; Even, S.; Cederbaum, I. (1967), "An algorithm for planarity testing of graphs", Theory of Graphs (Internat. Sympos., Rome, 1966), New York: Gordon and Breach, pp. 215–232, MR   0220617 .
  4. 1 2 3 Maon, Y.; Schieber, B.; Vishkin, U. (1986), "Parallel ear decomposition search (EDS) and ST-numbering in graphs", Theoretical Computer Science , 47 (3): 277–298, doi: 10.1016/0304-3975(86)90153-2 , MR   0882357 .
  5. ↑ Platt, C. R. (1976), "Planar lattices and planar graphs", Journal of Combinatorial Theory , Ser. B, 21 (1): 30–39, doi:10.1016/0095-8956(76)90024-1 .
  6. ↑ Di Battista, Giuseppe; Tamassia, Roberto (1988), "Algorithms for plane representations of acyclic digraphs", Theoretical Computer Science , 61 (2–3): 175–198, doi:10.1016/0304-3975(88)90123-5 .
  7. ↑ Ebert, J. (1983), "st-ordering the vertices of biconnected graphs", Computing , 30 (1): 19–33, doi:10.1007/BF02253293, MR   0691948, S2CID   6570953 .
  8. ↑ Even, Shimon; Tarjan, Robert Endre (1976), "Computing an st-numbering", Theoretical Computer Science , 2 (3): 339–344, doi:10.1016/0304-3975(76)90086-4, MR   0414406 .
  9. 1 2 Tarjan, Robert Endre (1986), "Two streamlined depth-first search algorithms" (PDF), Fundamenta Informaticae , 9 (1): 85–94, doi:10.3233/FI-1986-9105, MR   0848212 .
  10. ↑ Gazit, Hillel (1991), "Optimal EREW parallel algorithms for connectivity, ear decomposition and st-numbering of planar graphs", Proc. 5th International Parallel Processing Symposium, pp. 84–91, doi:10.1109/IPPS.1991.153761, S2CID   34959564 .
  11. 1 2 3 4 Schlipf, Lena; Schmidt, Jens M. (2019), "Simple computation of st-edge- and st-numberings from ear decompositions", Information Processing Letters , 145: 58–63, doi:10.1016/j.ipl.2019.01.008, S2CID   71714734 .
  12. ↑ Papamanthou, Charalampos; Tollis, Ioannis G. (2006), "Applications of parameterized st-orientations in graph drawing algorithms" (PDF), Graph Drawing: 13th International Symposium, GD 2005, Limerick, Ireland, September 12–14, 2005, Revised Papers , Lecture Notes in Computer Science, vol. 3843, Berlin: Springer, pp. 355–367, doi: 10.1007/11618058_32 , MR   2244524 .
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.