Bibliography

[BB96]

Gilles Brassard and Paul Bratley. Fundamentals of Algorithmics. Prentice-Hall, New Jersey, 1996.

[BDB91]

Paola Bertolazzi and Giuseppe Di Battista. On upward drawing testing of triconnected digraphs (extended abstract). In Proceedings of 7th ACM Symposium on Computational Geometry, pages 272-280. ACM Press, 1991.
[ http | http ]

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 edges point upward. The problem arises in the fields of ordered sets and automatic graph drawing and was open from several years. The time complexity of the proposed algorithm is O(n+r³log r) where n is the number of vertices and r is the number of sources and sinks of the digraph.

[BDBD98]

Paola Bertolazzi, Giuseppe Di Battista, and Walter Didimo. Quasi-upward planarity (extended abstract). In Proceedings of Graph Drawing '98, pages 15-29. Springer, 1998.
[ http | .pdf ]

In this paper we introduce the quasi-upward planr drawing convention and give a polynomial time algorithm for computing a quasi-upward planar drawing with the minimum numebr of bends within a given planar embedding. Further, we study the problem of computing quasi-upward planar drawings with the minimum number of bends of digraphs considering all the possible planar embeddings. The paper contains also experimental results about the proposed techniques.

[BDBD02]

Paola Bertolazzi, Giuseppe Di Battista, and Walter Didimo. Quasi-upward planarity. Algorithmica, 32:474-506, 2002.
[ http | .pdf ]

An upward planar drawing of a directed graph (digraph) is a planar drawing such that all the edges are represented by curves monotonically increasing in the vertical direction. In this paper we introduce and study the concept of quasi-upward planarity. Quasi-upward planarity allows us to extend the upward planarity theory to a large class of digraphs including digraphs that also have directed cycles. First, we characterize the digraphs that have a quasi-upward planar drawing. Second, we give a polynomial time algorithm for computing ``optimal'' quasi-upward planar drawings within a given planar embedding. Further, we apply branch and bound techniques to the problem of computing optimal quasi-upward planar drawings, considering all possible planar embeddings. The paper also contains experimental results about the proposed techniques.

[BDBLM94]

Paola Bertolazzi, Giuseppe Di Battista, Giuseppe Liotta, and Carlo Mannino. Upward drawings of triconnected digraphs. Algorithmica, 12:476-497, 1994.

[BDBMT98]

Paola Bertolazzi, Giuseppe Di Battista, Carlo Mannino, and Roberto Tamassia. Optimal upward planarity testing of single-source digraphs. SIAM Journal on Computing, 27(1):132-196, 1998.
[ http | .ps | .pdf ]

A digraph is upward planar if it has a planar drawing such that all the edges are monoton with respect to the vertical direction. Testing upward planarity and constructing upward planar drawings is important for displaying hiererchical network structures, which frequently arise in software engineering, project management, and visual languages. In this paper we investigate upward planarity and give an optimal algorithm for upward planarity testing. Our algorithm tests whether a single-sounce digraph with n vertices is upward planar in O(n) sequential time, and in O(log n) time on a CRCW PRAM with n log log n / log n processors using O(n) space. The algorithm also constructs in upward planar drawing if the test is successful. The previously known best result is an O(n²)-time algorithm bi Hutton ald Lubiw. No efficient parallel algorithms for upward planarity were previously known.

Keywords: graph drawing, planar graph, upward graph, triconnected components, parallel algorithm

[BFR98]

R. Balasubramanian, Michael R. Fellows, and Venkatesh Raman. An improved fixed parameter algorithm for vertex cover. Information Processing Letters, 65(3):163-168, 1998.

[BM76]

John Adrian Bondy and U. S. R. Murty. Graph Theory with Applications. North Holland, New York, 1976.

[CLRS01]

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. McGraw-Hill Book Company, second edition, 2001.

[DBETT99]

Giuseppe Di Battista, Peter Eades, Roberto Tamassia, and Ioannis G. Tollis. Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall, New Jersey, 1999.

[DBL98]

Giuseppe Di Battista and Giuseppe Liotta. Upward planarity checking: ``Faces are more than polygons'' (extended abstract). In Sue H. Whitesides, editor, Proceedings of Graph Drawing '98, volume 1547 of Lecture Notes in Computer Science, pages 72-86. Springer-Verlag, 1998.
[ http | .pdf ]

In this paper we look at upward planarity from a new perspective. Namely, we study the problem of checking whether a given drawing is upward planar. Our checker exploits the relationships between topology and geometry of upward planar drawings to verify the upward planarity of a significant family of drawings. The checker is simple and optimal both in terms of efficiency and in terms of degree.

[DBLR90]

Giuseppe Di Battista, Wei-Ping Liu, and Ivan Rival. Bipartite graphs, upward drawings, and planarity. Information Processing Letters, 36:317-322, 1990.

We show that a bipartite graph admits an upward drawing, i.e., a planar drawing with the additional constraint that all the edges flow in the same direction ifa and only if it is planar. This result finds applications both in the field of automatic graph layout and in the field of ordered sets.

Keywords: automatic graph drawing, ordered sets, planarity

[DBT88]

Giuseppe Di Battista and Roberto Tamassia. Algorithms for plane representations of acyclic digraphs. Theoretical Computer Science, 61:175-198, 1988.

Acyclic digraphs are widely used for representing hierarchical structures. Examples include PERT networks, subroutine-call graphs, family trees, organization charts, Hasse diagrams, and ISA hierarchies in knowledge representation diagrams. We investigate the problem of representing acyclic digraphs in the plane such that all edges flow in the same direction, e.g., from the left to the right or from the bottom to the top. Three plane representations are considered: straight drawings, visibility representations, and grid drawings. We provide efficient algorithms that construct these representations with all edges flowing in the same direction. The time complexity is O(n) for visibility representations and grid drawings, and O(n log n) for straight drawings, where n is the number of vertices of the digraph. For covering digraphs of lattices, the complexity of consturcting straight drawings is O(n). We also show that the planar digraphs that admit any one of these representations are exactly the subgraphs of planar st-graphs.

[DBTT92]

Giuseppe Di Battista, Roberto Tamassia, and Ioannis G. Tollis. Area requirement and symmetry display of planar upward drawings. Discrete and Computational Geometry, 7:381-401, 1992.

In this paper we investigate the problem of constructing planar stright-line drawings of acyclic digraphs such that all the edges flow in the same direction, e.g., from bottom to top. Our contribution is twofold. First we show the existence of a family of planar acyclic digraphs that require exponential area for any such drawing. Second, motivated by the preceding lower bound, we relax the straight-line constraint and allow bends along the edges. We present a linear-time algorithm that produces drawings of planar st-graphs with a small number of bends, asymptotically optimal area, and such that symmetries and isomorphisms of the digraph are displayed. If the digraph has no transitive edges, then the drawing obtained has no bends. Also, a variation of the algorithm produces drawings with exact minimum area.

[DF97]

Rod G. Downey and Michael R. Fellows. Parameterized Complexity. Monographs in Computer Science. Springer, New York, 1997.

[Die00]

Reinhard Diestel. Graph Theory, volume 173 of Graduate Texts in Mathematics. Springer, New York, 2nd edition, 2000.

[DMW02]

Vida Dujmovic, Pat Morin, and David R. Wood. Path-width and three-dimensional straight-line grid drawings of graphs. In Stephen G. Kobourov and Michael T. Goodrich, editors, Proceedings of Graph Drawing 2002, volume 2528 of Lecture Notes in Computer Science, pages 42-53. Springer, 2002.

[DW02]

Vida Dujmovic and Sue Whitesides. An efficient fixed parameter tractable algorithm for 1-sided crossing minimization. In Stephen G. Kobourov and Michael T. Goodrich, editors, Proceedings of Graph Drawing 2002, volume 2528 of Lecture Notes in Computer Science, pages 118-129. Springer, 2002.

[F48]

I. Fáry. On straight lines representation of planar graphs. Acta scientiarum mathematicarum, 11:229-233, 1948.

[GT95a]

Ashim Garg and Roberto Tamassia. On the computational complexity of upward and rectiliniar planarity testing (extended abstract). In Roberto Tamassia and Ioannis G. Tollis, editors, Proceedings of Graph Drawing '94, volume 894 of Lecture Notes in Computer Science, pages 286-297. Springer-Verlag, 1995.

A directed graph is upward planar if it can be drawn in the plane such than every edge is a monotonically increasing curve in the vertical direction, and no two edges cross. An undirected graph is rectilinear planar if it can be drawn in the plane such that every edge is a horizontal or vertical segment, and no two edges cross. Testing upward planarity and rectilinear planarity are fundamental problems in the effective visualization of various graph and network structures. In this paper we show that upward planarity testing and rectilinear planarity testing are NP-complete problems. We also show that it its NP-hard to approximate the minimum number of bends in a planar orthogonal drawing of an n-vertex graph with an O(n^1-epsilon) error, for any epsilon > 0.

[GT95b]

Ashim Garg and Robeto Tamassia. Upward planarity testing. Order, 12, 1995.
[ .ps.gz ]

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 cases of digraphs, such as embedded digraphs and single-source digraphs. We also sketch eth proof of NP-completeness of upward planarity testing.

[GT01]

Ashim Garg and Roberto Tamassia. On the computational complexity of upward and rectilinear planarity testing. SIAM Journal on Computing, 31(2):601-625, 2001.
[ http | .ps | .pdf ]

A directed graph is upward planar if it can be drawn in the plane such than every edge is a monotonically increasing curve in the vertical direction, and no two edges cross. An undirected graph is rectilinear planar if it can be drawn in the plane such that every edge is a horizontal or vertical segment, and no two edges cross. Testing upward planarity and rectilinear planarity are fundamental problems in the effective visualization of various graph and network structures. In this paper we show that upward planarity testing and rectilinear planarity testing are NP-complete problems. We also show that it its NP-hard to approximate the minimum number of bends in a planar orthogonal drawing of an n-vertex graph with an O(n^1-epsilon) error, for any epsilon > 0.

Keywords: graph drawing, planar drawing, upward drawing, rectilinear drawing, orthogonal drawing, layout, ordered set, planar graph, algorithm, computational complexity, NP-complete problem, approximation algorithm

[HL96]

Michael D. Hutton and Anna Lubiw. Upward planar drawing of single source acyclic digraphs. SIAM Journal on Computing, 25(2):291-311, 1996.
[ .pdf ]

An upward plane drawing of a directed acyclic graph is a plane drawing of the digraph in which each directed edge is represented as a curve monotone increasing in the vertical direction. Thomassen has given a non-algorithmic, graph-theoretic characterization of those directed graphs with a single source that admit an upward plane drawing. We present an efficient algorithm to test whether a given single-source acyclic digraph has an upward plane drawing and, if so, to find a representation of one such drawing. This resurt is made more significant in light of the recent proof, by Garg and Tamassia, that the problem is NP-complete for general digraphs.

The algorithm decomposes the digraph into biconnected and triconnected components, and defines conditions for merging the compenents into an upward plane drawing of the original digraph. To handle the triconnected components we provide a linear algorithm to test whether a given plane drawing of a single source digraph admits an upward plane drawing with the same faces and outer face, which also gives a simpler algorithmic proof of Thomassen's result. The entire testing algorithm (for general single-source directed acyclic graphs) operates in O(n²) time and O(n) space (n being the number of vertices in the input digraph) and represents the first polynomial time solution to the problem.

Keywords: algorithms, upward planar, graph drawing, graph embedding, graph decomposition, graph recognition, planar graph, directed graph

[HT72]

John Hopcroft and Robert E. Tarjan. Dividing a graph into triconnected compononts. SIAM Journal on Computing, 2:136-158, 1972.

[HT74]

John Hopcroft and Robert E. Tarjan. Efficient planarity testing. Journal of the ACM, 21(4):549-568, 1974.

This paper describes an efficient algorithm to determine whether an arbitrary graph G can be embedded in the plane. The algorithm may be viewed as an iterative version of a method originally proposed by L. Auslander and S. V. Parter and correctly formulated by A. J. Goldstein. The algorithm uses depth-first search and has O(V) time and space bounds, where V is the number of vertices in G. An ALGOL implementation of the algorithm successfully tested graphs with as many as 900 vertices in less than 12 seconds.

Keywords: computer programming - Subroutines; mathematical techniques

[JLM98]

Michael Jünger, Sebastian Leipert, and Petra Mutzel. Level planarity testing in linear time. In S. Whitesides, editor, Proc. Graph Drawing: 6th International Symposium (GD'98), volume 1547 of Lecture Notes in Computer Science, pages 224-237. Springer, 1998.

[KW01]

Michael Kaufmann and Dorothea Wagner, editors. Drawing Graphs: Methods and Models, volume 2025 of Lecture Notes in Computer Science Tutorial. Springer, 2001.

[Pap95]

Achilleas Papakostas. Upward planarity testing of outerplanar dags (extended abstract). In Roberto Tamassia and Ioannis G. Tollis, editors, Proceedings of Graph Drawing '94, volume 894 of Lecture Notes in Computer Science, pages 298-306. Springer, 1995.

In this paper, we present two polynomial-time algorithms to determine if an outerplanar directed acyclic graph (odag) can be drawn upward planar, that is, drawn in planar stright-line fashion so that all arcs point up. The first algorithm checks if the odag has an upward planar drawing that is topologically equivalent to the outerplanar embedding of the odag. This algorithm runs in linear time (which is optimal), and is faster than any previous algorithm known. The second algorithm also checks whether an odag has an upward planar drawing but does not insist that the drawing be topologically equivalent to the outerplanar embedding. This is the first polynomial-time algorithm we know of to solve this problem.

[Pla76]

C. R. Platt. Planar lattices and planar graphs. Journal of Combinatorial Theory (B), 21:30-39, 1976.

It is shown that a finite lattice is planar if and only if the (undirected) graph obtained from its (Hasse) diagram by adding an edge between its least and greatest elements is a planar graph.

[Roy88]

H. L. Royden. Real Analysis. Prentice-Hall, New Jersey, third edition, 1988.

[Ste51]

S. K. Stein. Convex maps. Proceedings of the American Mathematical Society, 1951:464-466, 1951.

[Tar72]

Robert E. Tarjan. Depth-first searcth and linear graph algorithms. SIAM Journal on Computing, 1(2):145-159, 1972.

[Tho89]

Carsten Thomassen. Planar acyclic oriented graphs. Order, 5:349-361, 1989.

A plane Hasse representation of an acyclic oriented graph is a drawing of the grah in the Euclidean plane such that all arcs are straight-line segments directed upwards and such that no two arks cross. We characterize completely those oriented graphs which have a plane Hasse representation such that all faces are bounded by convex polygons. From this we derive the Hasse representation analogue, due to Kelly and Rival, of Fary's theorem on straight-line representations of planar graphs and the Kurotowski type theorem of Platt for acyclic oriented graphs with only one source and one sink. Finally, we describe completely those acyclic oriented graphs which have a vertex dominating all other vertices and which have no plane Hasse representation, a problem posed by Trotter.

Keywords: Convex Hasse representation, Kurotowski type results for Hasse diagrams

[TT86]

Roberto Tamassia and Ioannis G. Tollis. A unified approach to visibility representations of planar graphs. Discrete and Computational Geometry, 1(4):321-341, 1986.

We study visibility representations of graphs, which are constructed by mapping vertices to horizontal segments, and edges to vertical segments that intersect only adjacent vertex-segments. Every graph that admits this representation must be planar. We consider three types of visibility representations, and we give complete characterizations of te classes of graphs that admit them. Furthermore, we present linear time algorithms for testing the existenc of and constructing visibility representations of planar graphs. Many applications of our results can be found in VLSI layout.

[Wag36]

K. Wagner. Bemerkungen zum vierfarbenproblem. Jahresbericht der Deutschen Mathematiker-Vereinigung, 46:26-32, 1936.

[Whi33]

Hassler Whitney. A set of topological invariants for graphs. American Journal of Mathematics, 55:231-235, 1933.

[Zho01]

Peng Zhou. Drawing graphs of bounded treewidth/pathwidth. Master's thesis, University of Auckland, 2001.