Upward planar drawing

Last updated
An upward planar drawing Upward planar drawing.svg
An upward planar drawing
This planar DAG has no upward drawing, because its source and sink cannot both be in the same face. Not upward planar.svg
This planar DAG has no upward drawing, because its source and sink cannot both be in the same face.

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

Contents

Characterizations

A directed acyclic graph must be planar in order to have an upward planar drawing, but not every planar acyclic graph has such a drawing. Among the planar directed acyclic graphs with a single source (vertex with no incoming edges) and sink (vertex with no outgoing edges), the graphs with upward planar drawings are the st-planar graphs, planar graphs in which the source and sink both belong to the same face of at least one of the planar embeddings of the graph. More generally, a graph G has an upward planar drawing if and only if it is directed and acyclic, and is a subgraph of an st-planar graph on the same vertex set. [2]

In an upward embedding, the sets of incoming and outgoing edges incident to each vertex are contiguous in the cyclic ordering of the edges at the vertex. A planar embedding of a given directed acyclic graph is said to be bimodal when it has this property. Additionally, the angle between two consecutive edges with the same orientation at a given vertex may be labeled as small if it is less than π, or large if it is greater than π. Each source or sink must have exactly one large angle, and each vertex that is neither a source nor a sink must have none. Additionally, each internal face of the drawing must have two more small angles than large ones, and the external face must have two more large angles than small ones. A consistent assignment is a labeling of the angles that satisfies these properties; every upward embedding has a consistent assignment. Conversely, every directed acyclic graph that has a bimodal planar embedding with a consistent assignment has an upward planar drawing, that can be constructed from it in linear time. [3]

Another characterization is possible for graphs with a single source. In this case an upward planar embedding must have the source on the outer face, and every undirected cycle of the graph must have at least one vertex at which both cycle edges are incoming (for instance, the vertex with the highest placement in the drawing). Conversely, if an embedding has both of these properties, then it is equivalent to an upward embedding. [4]

Computational complexity

Several special cases of upward planarity testing are known to be possible in polynomial time:

However, it is NP-complete to determine whether a planar directed acyclic graph with multiple sources and sinks has an upward planar drawing. [17]

Straight-line drawing and area requirements

Fáry's theorem states that every planar graph has a drawing in which its edges are represented by straight line segments, and the same is true of upward planar drawing: every upward planar graph has a straight upward planar drawing. [18] A straight-line upward drawing of a transitively reduced st-planar graph may be obtained by the technique of dominance drawing, with all vertices having integer coordinates within an n × n grid. [19] However, certain other upward planar graphs may require exponential area in all of their straight-line upward planar drawings. [18] If a choice of embedding is fixed, even oriented series parallel graphs and oriented trees may require exponential area. [20]

Hasse diagrams

Upward planar drawings are particularly important for Hasse diagrams of partially ordered sets, as these diagrams are typically required to be drawn upwardly. In graph-theoretic terms, these correspond to the transitively reduced directed acyclic graphs; such a graph can be formed from the covering relation of a partial order, and the partial order itself forms the reachability relation in the graph. If a partially ordered set has one minimal element, has one maximal element, and has an upward planar drawing, then it must necessarily form a lattice, a set in which every pair of elements has a unique greatest lower bound and a unique least upper bound. [21] The Hasse diagram of a lattice is planar if and only if its order dimension is at most two. [22] However, some partial orders of dimension two and with one minimal and maximal element do not have an upward planar drawing (take the order defined by the transitive closure of ).

Related Research Articles

<span class="mw-page-title-main">Graph drawing</span> Visualization of node-link graphs

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, cartography, linguistics, and bioinformatics.

<span class="mw-page-title-main">Hasse diagram</span> Visual depiction of a partially ordered set

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 one represents each element of as a vertex in the plane and draws a line segment or curve that goes upward from one vertex to another vertex whenever covers . These curves may cross each other but must not touch any vertices other than their endpoints. Such a diagram, with labeled vertices, uniquely determines its partial order.

<span class="mw-page-title-main">Feedback arc set</span> Edges that hit all cycles in a graph

In graph theory and graph algorithms, a feedback arc set or feedback edge set in a directed graph is a subset of the edges of the graph that contains at least one edge out of every cycle in the graph. Removing these edges from the graph breaks all of the cycles, producing an acyclic subgraph of the given graph, often called a directed acyclic graph. A feedback arc set with the fewest possible edges is a minimum feedback arc set and its removal leaves a maximum acyclic subgraph; weighted versions of these optimization problems are also used. If a feedback arc set is minimal, meaning that removing any edge from it produces a subset that is not a feedback arc set, then it has an additional property: reversing all of its edges, rather than removing them, produces a directed acyclic graph.

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

<span class="mw-page-title-main">Peripheral cycle</span> Graph cycle which does not separate remaining elements

In graph theory, a peripheral cycle in an undirected graph is, intuitively, a cycle that does not separate any part of the graph from any other part. Peripheral cycles were first studied by Tutte (1963), and play important roles in the characterization of planar graphs and in generating the cycle spaces of nonplanar graphs.

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.

<span class="mw-page-title-main">Layered graph drawing</span> Graph drawing with vertices in horizontal layers

Layered graph drawing or hierarchical graph drawing is a type of graph drawing in which the vertices of a directed graph are drawn in horizontal rows or layers with the edges generally directed downwards. It is also known as Sugiyama-style graph drawing after Kozo Sugiyama, who first developed this drawing style.

<span class="mw-page-title-main">Angular resolution (graph drawing)</span> Sharpest angle between edges at a vertex

In graph drawing, the angular resolution of a drawing of a graph is the sharpest angle formed by any two edges that meet at a common vertex of the drawing.

In graph drawing, a universal point set of order n is a set S of points in the Euclidean plane with the property that every n-vertex planar graph has a straight-line drawing in which the vertices are all placed at points of S.

<span class="mw-page-title-main">Arc diagram</span> Graph drawing with vertices on a line

An arc diagram is a style of graph drawing, in which the vertices of a graph are placed along a line in the Euclidean plane, with edges being drawn as semicircles in one or both of the two halfplanes bounded by the line, or as smooth curves formed by sequences of semicircles. In some cases, line segments of the line itself are also allowed as edges, as long as they connect only vertices that are consecutive along the line. Variations of this drawing style in which the semicircles are replaced by convex curves of some other type are also commonly called arc diagrams.

In graph theory, a bipolar orientation or st-orientation of an undirected graph is an assignment of a direction to each edge 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.

<span class="mw-page-title-main">Dominance drawing</span> Graph where coordinates show reachability

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 is reachable from another vertex u if and only if both Cartesian coordinates of v are greater than or equal to the coordinates of u. The edges of a dominance drawing may be drawn either as straight line segments, or, in some cases, as polygonal chains.

Anna Lubiw is a computer scientist known for her work in computational geometry and graph theory. She is currently a professor at the University of Waterloo.

In the mathematical field of graph theory, planarization is a method of extending graph drawing methods from planar graphs to graphs that are not planar, by embedding the non-planar graphs within a larger planar graph.

In graph drawing, the area used by a drawing is a commonly used way of measuring its quality.

In graph drawing styles that represent the edges of a graph by polylines, it is desirable to minimize the number of bends per edge or the total number of bends in a drawing. Bend minimization is the algorithmic problem of finding a drawing that minimizes these quantities.

<span class="mw-page-title-main">Clustered planarity</span>

In graph drawing, a clustered planar graph is a graph together with a hierarchical clustering on its vertices, such that the graph can be drawn together with a collection of simple closed curves surrounding each cluster with no crossings between graph edges or clusters.

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.

Simultaneous embedding is a technique in graph drawing and information visualization for visualizing two or more different graphs on the same or overlapping sets of labeled vertices, while avoiding crossings within both graphs. Crossings between an edge of one graph and an edge of the other graph are allowed.

References

Footnotes
  1. Garg & Tamassia (1995); Di Battista et al. (1998).
  2. Garg & Tamassia (1995), pp. 111–112; Di Battista et al. (1998), 6.1 "Inclusion in a Planar st-Graph", pp. 172–179; Di Battista & Tamassia (1988); Kelly (1987).
  3. Garg & Tamassia (1995), pp. 112–115; Di Battista et al. (1998), 6.2 "Angles in Upward Drawings", pp. 180–188; Bertolazzi & Di Battista (1991); Bertolazzi et al. (1994).
  4. Garg & Tamassia (1995), p. 115; Di Battista et al. (1998), 6.7.2 "Forbidden Cycles for Single-Source Digraphs", pp. 209–210; Thomassen (1989).
  5. Garg & Tamassia (1995), p. 119; Di Battista et al. (1998), p. 179.
  6. Garg & Tamassia (1995), pp. 119–121; Di Battista et al. (1998), 6.3 "Upward Planarity Testing of Embedded Digraphs", pp. 188–192; Bertolazzi & Di Battista (1991); Bertolazzi et al. (1994); Abbasi, Healy & Rextin (2010).
  7. Di Battista et al. (1998), pp. 191–192; Bertolazzi & Di Battista (1991); Bertolazzi et al. (1994).
  8. Garg & Tamassia (1995), pp. 125–126; Di Battista et al. (1998), 6.7.1 "Outerplanar Digraph", p. 209; Papakostas (1995).
  9. 1 2 3 Di Battista et al. (1998), 6.7.4 "Some Classes of Upward Planar Digraphs", p. 212.
  10. Didimo, Giordano & Liotta (2009).
  11. Di Battista, Liu & Rival (1990).
  12. Garg & Tamassia (1995), pp. 122–125; Di Battista et al. (1998), 6.5 "Optimal Upward Planarity Testing of Single-Source Digraphs", pp. 195–200; Hutton & Lubiw (1996); Bertolazzi et al. (1998).
  13. Chan (2004); Healy & Lynch (2006).
  14. Healy & Lynch (2006).
  15. Chaplick et al. (2022)
  16. Jünger & Leipert (1999).
  17. Garg & Tamassia (1995), pp. 126–132; Di Battista et al. (1998), 6.6 "Upward Planarity Testing is NP-complete", pp. 201–209; Garg & Tamassia (2001).
  18. 1 2 Di Battista & Frati (2012); Di Battista, Tamassia & Tollis (1992).
  19. Di Battista et al. (1998), 4.7 "Dominance Drawings", pp. 112–127; Di Battista, Tamassia & Tollis (1992).
  20. Di Battista & Frati (2012); Bertolazzi et al. (1994); Frati (2008).
  21. Di Battista et al. (1998), 6.7.3 "Forbidden Structures for Lattices", pp. 210–212; Platt (1976).
  22. Garg & Tamassia (1995), pp. 118; Baker, Fishburn & Roberts (1972).
Surveys and textbooks
Research articles