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 ...

, an ''st''-planar graph is a

bipolar orientation 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 ' ...

of a

plane 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 cros ...

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.. 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 In the mathematical discipline of graph theory, the dual graph of a plane graph is a graph that has a vertex for each face of . The dual graph has an edge for each pair of faces in that are separated from each other by an edge, and a self-loo ...

(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.

Order theory

These graphs are closely related to

partially ordered set In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binar ...

s and lattices. 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 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 In mathematics, the dimension of a partially ordered set (poset) is the smallest number of total orders the intersection of which gives rise to the partial order. This concept is also sometimes called the order dimension or the Dushnik–Miller d ...

of a partially ordered set is the least number of

total order In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X: # a \leq a ( reflexiv ...

s 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 In the mathematical field of graph theory, a transitive reduction of a directed graph is another directed graph with the same vertices and as few edges as possible, such that for all pairs of vertices , a (directed) path from to in exists i ...

of the given graph. Conversely, the Hasse diagram of every two-dimensional complete lattice is always an ''st''-planar graph.

Graph drawing

Based on this two-dimensional partial order property, every ''st''-planar graph can be given a

dominance drawing Dominance drawing is a style of graph drawing of directed acyclic graphs that makes the reachability relations between vertices visually apparent. In dominance drawing, vertices are placed at distinct points of the Euclidean plane and a vertex ''v ...

, 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''. The coordinates of such a drawing may also be used as a

data structure In computer science, a data structure is a data organization, management, and storage format that is usually chosen for Efficiency, efficient Data access, access to data. More precisely, a data structure is a collection of data values, the rel ...

that can be used to test whether one vertex of an ''st''-planar graph can reach another in

constant 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 ...

per query. Rotating such a drawing by 45° gives 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 ...

of the graph. A directed acyclic graph ''G'' has an

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

References

{{reflist Planar graphs