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+r3log r) where n is the number of vertices and r is the number of sources and sinks of the digraph.
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.
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.
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(n2)-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
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.
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
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.
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.
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(n1-epsilon) error, for any epsilon > 0.
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.
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(n1-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
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(n2) 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
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
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.
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.
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
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.