A Survey on Graph Drawing Beyond Planarity <s> Upward RAC drawings. <s> Abstract 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 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. 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 constructing 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 . <s> BIB001 </s> A Survey on Graph Drawing Beyond Planarity <s> Upward RAC drawings. <s> In this paper we investigate the problem of constructing planar straight-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 planarst-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. <s> BIB002 </s> A Survey on Graph Drawing Beyond Planarity <s> Upward RAC drawings. <s> A directed graph is upward planar if it can be drawn in the plane such that 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 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, for any ∈>0. <s> BIB003 </s> A Survey on Graph Drawing Beyond Planarity <s> Upward RAC drawings. <s> In this paper we introduce the quasi-upward planar drawing convention and give a polynomial time algorithm for computing a quasi-upward planar drawing with the minimum number 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. <s> BIB004 </s> A Survey on Graph Drawing Beyond Planarity <s> Upward RAC drawings. <s> Note: Special Issue on Selected Papers from GD '09. Accepted, subject to minor revisions Reference EPFL-ARTICLE-158708 Record created on 2010-11-26, modified on 2017-05-12 <s> BIB005 </s> A Survey on Graph Drawing Beyond Planarity <s> Upward RAC drawings. <s> Mixed graphs have both directed and undirected edges and have received considerable attention in the literature. We study two upward planarity testing problems for embedded mixed graphs, give some NP-hardness results, and describe Integer Linear Programming techniques to solve them. Experiments show the efficiency of our approach. <s> BIB006 </s> A Survey on Graph Drawing Beyond Planarity <s> Upward RAC drawings. <s> Upward graph drawing is concerned with computing two-dimensional layouts of directed graphs where all edges flow in the upward direction. Namely, given a directed graph G.V;E/ (also called a digraph for short), an upward drawing of G is a drawing such that: (i) each vertex v 2 V is mapped to a distinct point pv of the plane and (ii) each edge .u; v/ 2 E is drawn as a simple curve from pu and pv, monotonically increasing in the upward direction. Clearly, G admits an upward drawing only if it does not contain directed cycles; if we allow edge crossings, acyclicity is also a sufficient condition for the existence of an upward drawing. Instead, if G is planar and we require that also the upward drawing of G is crossing-free, acyclicity is only a necessary condition, and the upward drawability of G becomes a much more intriguing problem. An upward drawing with no edge crossing is called an upward planar drawing; deciding whether a planar digraph G admits such a drawing is recognized as the upward planarity testing problem. This problem can be studied in two different settings: <s> BIB007
In an upward drawing of a digraph, each edge is a curve monotonically increasing in the vertical direction (see, e.g.,  ). Upward drawings are used to visually convey the structure of acyclic digraphs and have also been extended to visualize other kinds of networks BIB004 BIB006 . Testing whether a given planar digraph admits an upward planar (i.e., crossing-free) drawing is one of the most studied problems in this context; refer to Didimo BIB007 for a survey. Although polynomial-time testing algorithms are known for specific subfamilies of planar digraphs or when the digraph has a fixed embedding, the testing problem is NP-complete in general BIB003 . Also, although a planar digraph has an upward planar drawing if and only if it has a straight-line upward planar drawing BIB001 , there are digraphs for which every straight-line upward planar drawing requires exponential area BIB001 BIB002 ; quadratic area is always achievable if we allow edge bends. Similar questions have been investigated for RAC drawings. Angelini et al. proved that deciding whether a planar acyclic digraph admits a straight-line upward RAC drawing is NP-hard and that the area required by an n-vertex straight-line upward RAC drawing may be exponential in n BIB005 .