Upward planar drawing

Last updated July 30, 2024

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.

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:

Testing whether a graph is st-planar may be accomplished in linear time by adding an edge from s to t and testing whether the remaining graph is planar. Along the same lines, it is possible to construct an upward planar drawing (when it exists) of a directed acyclic graph with a single source and sink, in linear time.^[5]
Testing whether a directed graph with a fixed planar embedding can be drawn upward planar, with an embedding consistent with the given one, can be accomplished by checking that the embedding is bimodal and modeling the consistent assignment problem as a network flow problem. The running time is linear in the size of the input graph, and polynomial in its number of sources and sinks.^[6]
Because oriented polyhedral graphs have a unique planar embedding, the existence of an upward planar drawing for these graphs may be tested in polynomial time.^[7]
Testing whether an outerplanar directed acyclic graph has an upward planar drawing is also polynomial.^[8]
Every series–parallel graph, oriented consistently with the series–parallel structure, is upward planar. An upward planar drawing can be constructed directly from the series–parallel decomposition of the graph.^[9] More generally, arbitrary orientations of undirected series–parallel graphs may be tested for upward planarity in polynomial time.^[10]
Every oriented tree is upward planar.^[9]
Every bipartite planar graph, with its edges oriented consistently from one side of the bipartition to the other, is upward planar^[9]^[11]
A more complicated polynomial time algorithm is known for testing upward planarity of graphs that have a single source, but multiple sinks, or vice versa.^[12]
Testing upward planarity can be performed in polynomial time when there are a constant number of triconnected components and cut vertices, and is fixed-parameter tractable in these two numbers.^[13] It is also fixed-parameter tractable in the cyclomatic number of the input graph.^[14] It is also fixed-parameter tractable in the number of sources (i.e. vertices with no in-edges)^[15]
If the y-coordinates of all vertices are fixed, then a choice of x-coordinates that makes the drawing upward planar can be found in polynomial time.^[16]

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 $a<b,a<c,b<d,b<e,c<d,c<e,d<f,e<f$ ).

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.

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

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.

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.

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.

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.

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.

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

↑ Garg & Tamassia (1995); Di Battista et al. (1998).
↑ 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).
↑ 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).
↑ Garg & Tamassia (1995), p. 115; Di Battista et al. (1998), 6.7.2 "Forbidden Cycles for Single-Source Digraphs", pp. 209–210; Thomassen (1989).
↑ Garg & Tamassia (1995), p. 119; Di Battista et al. (1998), p. 179.
↑ 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).
↑ Di Battista et al. (1998), pp. 191–192; Bertolazzi & Di Battista (1991); Bertolazzi et al. (1994).
↑ Garg & Tamassia (1995), pp. 125–126; Di Battista et al. (1998), 6.7.1 "Outerplanar Digraph", p. 209; Papakostas (1995).
1 2 3 Di Battista et al. (1998), 6.7.4 "Some Classes of Upward Planar Digraphs", p. 212.
↑ Didimo, Giordano & Liotta (2009).
↑ Di Battista, Liu & Rival (1990).
↑ 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).
↑ Chan (2004); Healy & Lynch (2006).
↑ Healy & Lynch (2006).
↑ Chaplick et al. (2022)
↑ Jünger & Leipert (1999).
↑ 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).
1 2 Di Battista & Frati (2012); Di Battista, Tamassia & Tollis (1992).
↑ Di Battista et al. (1998), 4.7 "Dominance Drawings", pp. 112–127; Di Battista, Tamassia & Tollis (1992).
↑ Di Battista & Frati (2012); Bertolazzi et al. (1994); Frati (2008).
↑ Di Battista et al. (1998), 6.7.3 "Forbidden Structures for Lattices", pp. 210–212; Platt (1976).
↑ Garg & Tamassia (1995), pp. 118; Baker, Fishburn & Roberts (1972).

Surveys and textbooks

Di Battista, Giuseppe; Eades, Peter; Tamassia, Roberto; Tollis, Ioannis G. (1998), "Flow and Upward Planarity", Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall, pp. 171–213, ISBN 978-0-13-301615-4 .
Di Battista, Giuseppe; Frati, Fabrizio (2012), "Drawing trees, outerplanar graphs, series–parallel graphs, and planar graphs in small area", Thirty Essays on Geometric Graph Theory, Algorithms and combinatorics, vol. 29, Springer, pp. 121–165, doi:10.1007/978-1-4614-0110-0_9, ISBN 9781461401100 . Section 5, "Upward Drawings", pp. 149–151.
Garg, Ashim; Tamassia, Roberto (1995), "Upward planarity testing", Order , 12 (2): 109–133, doi:10.1007/BF01108622, MR 1354797, S2CID 14183717 .

Research articles

Abbasi, Sarmad; Healy, Patrick; Rextin, Aimal (2010), "Improving the running time of embedded upward planarity testing", Information Processing Letters, 110 (7): 274–278, doi:10.1016/j.ipl.2010.02.004, MR 2642837 .
Baker, K. A.; Fishburn, P. C.; Roberts, F. S. (1972), "Partial orders of dimension 2", Networks, 2 (1): 11–28, doi:10.1002/net.3230020103 .
Bertolazzi, Paola; Cohen, Robert F.; Di Battista, Giuseppe; Tamassia, Roberto; Tollis, Ioannis G. (1994), "How to draw a series–parallel digraph", International Journal of Computational Geometry & Applications, 4 (4): 385–402, doi:10.1142/S0218195994000215, MR 1310911 .
Bertolazzi, Paola; Di Battista, Giuseppe (1991), "On upward drawing testing of triconnected digraphs", Proceedings of the Seventh Annual Symposium on Computational Geometry (SCG '91, North Conway, New Hampshire, USA), New York, NY, USA: ACM, pp. 272–280, doi:10.1145/109648.109679, ISBN 0-89791-426-0, S2CID 18306721 .
Bertolazzi, P.; Di Battista, G.; Liotta, G.; Mannino, C. (1994), "Upward drawings of triconnected digraphs", Algorithmica , 12 (6): 476–497, doi:10.1007/BF01188716, MR 1297810, S2CID 33167313 .
Bertolazzi, Paola; Di Battista, Giuseppe; Mannino, Carlo; Tamassia, Roberto (1998), "Optimal upward planarity testing of single-source digraphs", SIAM Journal on Computing , 27 (1): 132–169, doi:10.1137/S0097539794279626, MR 1614821 .
Chan, Hubert (2004), "A parameterized algorithm for upward planarity testing", Proc. 12th European Symposium on Algorithms (ESA '04) , Lecture Notes in Computer Science, vol. 3221, Springer-Verlag, pp. 157–168, doi:10.1007/978-3-540-30140-0_16, ISBN 978-3-540-23025-0 .
Di Battista, Giuseppe; Liu, Wei-Ping; Rival, Ivan (1990), "Bipartite graphs, upward drawings, and planarity", Information Processing Letters , 36 (6): 317–322, doi:10.1016/0020-0190(90)90045-Y, MR 1084490 .
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 , MR 0980241 .
Di Battista, Giuseppe; Tamassia, Roberto; Tollis, Ioannis G. (1992), "Area requirement and symmetry display of planar upward drawings", Discrete and Computational Geometry , 7 (4): 381–401, doi: 10.1007/BF02187850 , MR 1148953 .
Didimo, Walter; Giordano, Francesco; Liotta, Giuseppe (2009), "Upward spirality and upward planarity testing", SIAM Journal on Discrete Mathematics , 23 (4): 1842–1899, doi:10.1137/070696854, MR 2594962, S2CID 26154284 .
Frati, Fabrizio (2008), "On minimum area planar upward drawings of directed trees and other families of directed acyclic graphs", International Journal of Computational Geometry & Applications, 18 (3): 251–271, doi:10.1142/S021819590800260X, MR 2424444 .
Garg, Ashim; Tamassia, Roberto (2001), "On the computational complexity of upward and rectilinear planarity testing", SIAM Journal on Computing , 31 (2): 601–625, doi:10.1137/S0097539794277123, MR 1861292, S2CID 15691098 .
Healy, Patrick; Lynch, Karol (2006), "Two fixed-parameter tractable algorithms for testing upward planarity", International Journal of Foundations of Computer Science, 17 (5): 1095–1114, doi:10.1142/S0129054106004285 .
Hutton, Michael D.; Lubiw, Anna (1996), "Upward planar drawing of single-source acyclic digraphs", SIAM Journal on Computing , 25 (2): 291–311, doi:10.1137/S0097539792235906, MR 1379303 . First presented at the 2nd ACM-SIAM Symposium on Discrete Algorithms, 1991.
Jünger, Michael; Leipert, Sebastian (1999), "Level planar embedding in linear time", Graph Drawing (Proc. GD '99) , Lecture Notes in Computer Science, vol. 1731, pp. 72–81, doi: 10.1007/3-540-46648-7_7 , ISBN 978-3-540-66904-3 .
Kelly, David (1987), "Fundamentals of planar ordered sets", Discrete Mathematics , 63 (2–3): 197–216, doi: 10.1016/0012-365X(87)90008-2 , MR 0885497 .
Papakostas, Achilleas (1995), "Upward planarity testing of outerplanar dags (extended abstract)", Graph Drawing: DIMACS International Workshop, GD '94, Princeton, New Jersey, USA, October 10–12, 1994, Proceedings, Lecture Notes in Computer Science, vol. 894, Berlin: Springer, pp. 298–306, doi: 10.1007/3-540-58950-3_385 , ISBN 978-3-540-58950-1, MR 1337518 .
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 .
Thomassen, Carsten (1989), "Planar acyclic oriented graphs", Order , 5 (4): 349–361, doi:10.1007/BF00353654, MR 1010384, S2CID 121445872 .
Chaplick, Steven; Di Giacomo, Emilio; Frati, Fabrizio; Ganian, Robert; Raftopoulou, Chrysanthi N.; Simonov, Kirill (2022), "Parameterized Algorithms for Upward Planarity", 38th International Symposium on Computational Geometry, SoCG, Leibniz International Proceedings in Informatics (LIPIcs), vol. 224, pp. 26:1–26:16, doi: 10.4230/LIPIcs.SoCG.2022.26 , ISBN 9783959772273

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.

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

[special-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).

[fary-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).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]