# Upward planarity testing

@article{Garg1995UpwardPT, title={Upward planarity testing}, author={Ashim Garg and Roberto Tamassia}, journal={Order}, year={1995}, volume={12}, pages={109-133} }

Acyclic digraphs, such as the covering digraphs of ordered sets, are usually drawn upward, i.e., with the edges monotonically increasing in the vertical direction. A digraph is upward planar if it admits an upward planar drawing. In this survey paper, we overview the literature on the problem of upward planarity testing. We present several characterizations of upward planarity and describe upward planarity testing algorithms for special classes of digraphs, such as embedded digraphs and single… Expand

#### Figures from this paper

#### 61 Citations

Switch-Regular Upward Planarity Testing of Directed Trees

- Computer Science, Mathematics
- J. Graph Algorithms Appl.
- 2011

This paper investigates a new upward planarity testing problem, deciding whether a digraph admits an upward planar drawing having some special topological properties: such a drawing is called switchregular, and describes an optimal linear-time testing and embedding algorithm. Expand

Upward Planar Drawings of Series-Parallel Digraphs with Maximum Degree Three

- Mathematics, Computer Science
- WALCOM
- 2007

A linear-time algorithm is given to test the upward planarity of a series-parallel digraph G with maximum degree three and obtain an upward planar drawing of G if G admits one. Expand

Quasi-Upward Planarity

- Mathematics, Computer Science
- Algorithmica
- 2001

This paper gives a polynomial time algorithm for computing ``optimal'' quasi-upward planar drawings within a given planar embedding, and applies branch and bound techniques to the problem of computing optimal quasi- Upward Planarity drawings, considering all possible planarembeddings. Expand

Maximum upward planar subgraphs of embedded planar digraphs

- Computer Science, Mathematics
- Comput. Geom.
- 2008

It is proved that the addressed problem is NP-Hard and a fast heuristic and an exponential-time exact algorithm are described and a wide experimental analysis is performed to show the effectiveness of the techniques. Expand

Upward Spirality and Upward Planarity Testing

- Mathematics, Computer Science
- SIAM J. Discret. Math.
- 2009

The results use the new notion of upward spirality that, informally speaking, is a measure of the “level of winding” that a triconnected component of a digraph $G$ can have in an upward planar drawing of $G$. Expand

Maximum Upward Planar Subgraphs of Embedded Planar Digraphs

- Mathematics, Computer Science
- Graph Drawing
- 2007

It is proved that the addressed problem is NP-Hard, a fast heuristic and an exponential-time exact algorithm are described, and a wide experimental analysis is performed to show the effectiveness of the techniques. Expand

Upward Planarity Testing: A Computational Study

- Mathematics, Computer Science
- Graph Drawing
- 2013

An extensive experimental comparison between virtually all known approaches to the directed acyclic graph DAG problem is given, and a new SAT formulation based on a recent theoretical result by Fulek et al. turns out to perform best among all known algorithms. Expand

Finding Bimodal and Acyclic Orientations of Mixed Planar Graphs is NP-Complete

- Computer Science
- 2011

It is shown that this extendability problem is NP-complete by first determining its complexity in the fixed embedding setting and then extending the result to the variable embeddingSetting. Expand

Upward Planar Drawings and Switch-regularity Heuristics

- Mathematics, Computer Science
- J. Graph Algorithms Appl.
- 2006

A new characterization of switch-regular upward embeddings is presented, a concept introduced by Di Battista and Liotta in 1998, which allows for a new e‐cient algorithm for computing upward planar drawings of embedded planar digraphs. Expand

Upward planarization and layout

- Computer Science
- 2011

A novel upward planarization approach for upward crossing minimization of DAGs that utilizes new ideas for subgraph computation and arc reinsertion and a new layout approach for realizing UPRs, that is, a drawing algorithm for constructing upward drawings where the arc crossings arising in the drawing are the ones modeled by the dummy nodes in R. Expand

#### References

SHOWING 1-10 OF 31 REFERENCES

Optimal Upward Planarity Testing of Single-Source Digraphs

- Mathematics, Computer Science
- ESA
- 1993

This paper provides a new combinatorial characterization of upward planarity, and gives an optimal algorithm for upward planar testing of single-source digraphs, which was previously known. Expand

On upward drawing testing of triconnected digraphs (extended abstract)

- Computer Science, Mathematics
- SCG '91
- 1991

In this paper we solve, for triconnected digraphs, the problem of the existence of a P-time algorithm for testing if a digraph has an upward drawing, i.e. a drawing such that all the edges point… Expand

Upward Planarity Testing of Outerplanar Dags

- Mathematics, Computer Science
- Graph Drawing
- 1994

Two polynomial-time algorithms are presented to determine if an outerplanar directed acyclic graph (odag) can be drawn upward planar, that is, drawn in planar straight-line fashion so that all arcs point up. Expand

Area requirement and symmetry display of planar upward drawings

- Mathematics, Computer Science
- Discret. Comput. Geom.
- 1992

A linear-time algorithm is presented that produces drawings of planar acyclic digraphs with a small number of bends, asymptotically optimal area, and such that symmetries and isomorphisms of the digraph are displayed. Expand

On the Compuational Complexity of Upward and Rectilinear Planarity Testing

- Mathematics, Computer Science
- Graph Drawing
- 1994

This paper shows that upward planarity testing and rectilinear planar testing are NP-complete problems, and shows that it is NP-hard to approximate the minimum number of bends in a planar orthogonal drawing of an n-vertex graph with an O(n1−∈) error. Expand

Upward Planar Drawing of Single Source Acyclic Digraphs

- Mathematics, Computer Science
- Planar Graphs
- 1991

This work presents an algorithm to test whether a given single-source acyclic digraph has an upward plane drawing and, if so, to a representation of one such drawing and a proof of Thomassen's result. Expand

Bipartite Graphs, Upward Drawings, and Planarity

- Mathematics, Computer Science
- Inf. Process. Lett.
- 1990

Abstract We show that a bipartite digraph admits an upward drawing, i.e., a planar drawing with the additional constraint that all the edges flow in the same direction if and only if it is planar.… Expand

How to Draw a Series-Parallel Digraph

- Mathematics, Computer Science
- Int. J. Comput. Geom. Appl.
- 1994

The results show that while series-parallel digraphs have a rather simple and well understood combinatorial structure, naive drawing strategies lead to drawings with exponential area, and clever algorithms are needed to achieve optimal area. Expand

Algorithms for Plane Representations of Acyclic Digraphs

- Computer Science, Mathematics
- Theor. Comput. Sci.
- 1988

This work investigates the problem of representing acyclic digraphs in the plane in such a way that all edges flow in the same direction, e.g., from the left to the right or from the bottom to the top. Expand

Fundamentals of planar ordered sets

- Computer Science, Mathematics
- Discret. Math.
- 1987

It is proved it is equivalent to allow instead an arc from a to b as long as the arc does not go below the level of a or above thelevel of b (whenever a is covered by b ). Expand