st-planar graph

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

Within the drawing, each face of the graph must have the same structure: there is one vertex that acts as the source of the face, one vertex that acts as the sink of the face, and all edges within the face are directed along two paths from the source to the sink. If one draws an additional edge from the sink of an st-planar graph back to the source, through the outer face, and then constructs the dual graph (oriented each dual edge clockwise with respect to its primal edge) then the result is again an st-planar graph, augmented with an extra edge in the same way.[1]

These graphs are closely related to partially ordered sets and lattices. The Hasse diagram of a partially ordered set is a directed acyclic graph whose vertices are the set elements, with an edge from x to y for each pair x, y of elements for which x ≤ y in the partial order but for which there does not exist z with x ≤ y ≤ z. A partially ordered set forms a complete lattice if and only if every subset of elements has a unique greatest lower bound and a unique least upper bound, and the order dimension of a partially ordered set is the least number of total orders on the same set of elements whose intersection is the given partial order. If the vertices of an st-planar graph are partially ordered by reachability, then this ordering always forms a two-dimensional complete lattice, whose Hasse diagram is the transitive reduction of the given graph. Conversely, the Hasse diagram of every two-dimensional complete lattice is always an st-planar graph.[2]

Based on this two-dimensional partial order property, every st-planar graph can be given a dominance drawing, in which for every two vertices u and v there exists a path from u to v if and only if both coordinates of u are smaller than the corresponding coordinates of v.[3] The coordinates of such a drawing may also be used as a data structure that can be used to test whether one vertex of an st-planar graph can reach another in constant time per query. Rotating such a drawing by 45° gives an upward planar drawing of the graph. A directed acyclic graph G has an upward planar drawing if and only if G is a subgraph of an st-planar graph.[4]

References

  1. 1 2 Di Battista, Giuseppe; Eades, Peter; Tamassia, Roberto; Tollis, Ioannis G. (1998), "4.2 Properties of Planar Acyclic Digraphs", Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall, pp. 89–96, ISBN 978-0-13-301615-4.
  2. ↑ 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.
  3. ↑ Di Battista et al. (1998), 4.7 Dominance Drawings, pp. 112–127.
  4. ↑ 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.
This article is issued from Wikipedia - version of the Thursday, September 03, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.