Quasi‐Upward Planarity

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.