In 1999, Heath, Pemmaraju, and Trenk [SIAM J. Comput. 28(4), 1999] extended the classic notion of book embeddings to digraphs, introducing the concept of upward book embeddings, in which the vertices must appear along the spine in a topological order and the edges are partitioned into pages, so that no two edges in the same page cross. For a partitioned digraph G = (V, ⋃^k_{i=1} E_i), that is, a digraph whose edge set is partitioned into k subsets, an upward book embedding is required to assign edges to pages as prescribed by the given partition. In a companion paper, Heath and Pemmaraju [SIAM J. Comput. 28(5), 1999] proved that the problem of testing the existence of an upward book embedding of a partitioned digraph is linear-time solvable for k = 1 and recently Akitaya, Demaine, Hesterberg, and Liu [GD, 2017] have shown the problem NP-complete for k ≥ 3. In this paper, we study upward book embeddings of partitioned digraphs and focus on the unsolved case k = 2. Our first main result is a novel characterization of the upward embeddings that support an upward book embedding in two pages. We exploit this characterization in several ways, and obtain a rich picture of the complexity landscape of the problem. First, we show that the problem remains NP-complete when k = 2, thus closing the complexity gap for the problem. Second, we show that, for an n-vertex partitioned digraph with a prescribed planar embedding, the existence of an upward book embedding that respects the given planar embedding can be tested in O(n log³ n) time. Finally, leveraging the SPQ(R)-tree decomposition of biconnected graphs into triconnected components, we present a cubic-time testing algorithm for biconnected directed partial 2-trees.

We consider upward-planar layered drawings of directed graphs, i.e., crossing-free drawings in which each edge is drawn as a y-monotone curve going upward from its tail to its head, and the y-coordinates of the vertices are integers. The span of an edge in such a drawing is the absolute difference between the y-coordinates of its endpoints, and the span of the drawing is the maximum span of any edge. The span of an upward-planar graph is the minimum span over all its upward-planar drawings. We study the problem of determining the span of upward-planar graphs and provide both combinatorial and algorithmic results. On the combinatorial side, we present upper and lower bounds for the span of directed trees. On the algorithmic side, we show that the problem of determining the span of an upward-planar graph is NP-complete already for directed trees and for biconnected single-source graphs. Moreover, we give efficient algorithms for several graph families with a bounded number of sources, including st-planar graphs and graphs where the planar or upward-planar embedding is prescribed. Furthermore, we show that the problem is fixed-parameter tractable with respect to the vertex cover number and the treedepth plus the span.

This paper studies planar drawings of graphs in which each vertex is represented as a point along a sequence of horizontal lines, called levels, and each edge is either a horizontal segment or a strictly y -monotone curve. A graph is s -span weakly leveled planar if it admits such a drawing where the edges have span at most s ; the span of an edge is the number of levels it touches minus one. We investigate the problem of computing s -span weakly leveled planar drawings from both the computational and the combinatorial perspectives. We prove the problem to be para-NP-hard with respect to its natural parameter s and investigate its complexity with respect to widely used structural parameters. We show the existence of a polynomial-size kernel with respect to vertex cover number and prove that the problem is FPT when parameterized by treedepth. We also present upper and lower bounds on the span for various graph classes. Notably, we show that cycle trees, a family of 2-outerplanar graphs generalizing Halin graphs, are Θ(log n )-span weakly leveled planar and 4-span weakly leveled planar when 3-connected. As a byproduct of these combinatorial results, we obtain improved bounds on the edge-length ratio of the graph families under consideration.

A well-known result by Kant [Algorithmica, 1996] implies that n-vertex outerplane graphs admit embedding-preserving planar straight-line grid drawings where the internal faces are convex polygons in O(n²) area. In this paper, we present an algorithm to compute such drawings in O(n¹·⁵) area. We also consider outerplanar drawings in which the internal faces are required to be strictly-convex polygons. In this setting, we consider outerplanar graphs whose weak dual is a path and give a drawing algorithm that achieves Θ(nk²) area, where k is the maximum size of an internal facial cycle.

We study the following question, which has been considered since the 90’s: Does every st-planar graph admit a planar straight-line dominance drawing? We show concrete evidence for the difficulty of this question, by proving that, unlike upward planar straight-line drawings, planar straight-line dominance drawings with prescribed y-coordinates do not always exist and planar straight-line dominance drawings cannot always be constructed via a contract-draw-expand inductive approach. We also show several classes of st-planar graphs that always admit a planar straight-line dominance drawing. These include st-planar 3-trees in which every stacking operation introduces two edges incoming into the new vertex, st-planar graphs in which every vertex is adjacent to the sink, and st-planar graphs in which no face has the left boundary that is a single edge.

We study upward pointset embeddings (UPSEs) of planar $st$-graphs. Let $G$ be a planar $st$-graph and let $S \subset \mathbb{R}^2$ be a pointset with $|S|= |V(G)|$. An UPSE of $G$ on $S$ is an upward planar straight-line drawing of $G$ that maps the vertices of $G$ to the points of $S$. We consider both the problem of testing the existence of an UPSE of $G$ on $S$ (UPSE Testing) and the problem of enumerating all UPSEs of $G$ on $S$. We prove that UPSE Testing is NP-complete even for $st$-graphs that consist of a set of directed $st$-paths sharing only $s$ and $t$. On the other hand, if $G$ is an $n$-vertex planar $st$-graph whose maximum $st$-cutset has size $k$, then UPSE Testing can be solved in $O(n^{4k})$ time with $O(n^{3k})$ space; also, all the UPSEs of $G$ on $S$ can be enumerated with $O(n)$ worst-case delay, using $O(k n^{4k} \log n)$ space, after $O(k n^{4k} \log n)$ set-up time. Moreover, for an $n$-vertex $st$-graph whose underlying graph is a cycle, we provide a necessary and sufficient condition for the existence of an UPSE on a given pointset, which can be tested in $O(n \log n)$ time. Related to this result, we give an algorithm that, for a set $S$ of $n$ points, enumerates all the non-crossing monotone Hamiltonian cycles on $S$ with $O(n)$ worst-case delay, using $O(n^2)$ space, after $O(n^2)$ set-up time.

This paper studies planar drawings of graphs in which each vertex is represented as a point along a sequence of horizontal lines, called levels, and each edge is either a horizontal segment or a strictly $y$-monotone curve. A graph is $s$-span weakly leveled planar if it admits such a drawing where the edges have span at most $s$; the span of an edge is the number of levels it touches minus one. We investigate the problem of computing $s$-span weakly leveled planar drawings from both the computational and the combinatorial perspectives. We prove the problem to be para-NP-hard with respect to its natural parameter $s$ and investigate its complexity with respect to widely used structural parameters. We show the existence of a polynomial-size kernel with respect to vertex cover number and prove that the problem is FPT when parameterized by treedepth. We also present upper and lower bounds on the span for various graph classes. Notably, we show that cycle trees, a family of $2$-outerplanar graphs generalizing Halin graphs, are $Θ(\log n)$-span weakly leveled planar and $4$-span weakly leveled planar when $3$-connected. As a byproduct of these combinatorial results, we obtain improved bounds on the edge-length ratio of the graph families under consideration.

We show an O ( n ) -time reduction from the problem of testing whether a multiset of positive integers can be partitioned into two multisets so that the sum of the integers in each multiset is equal to n / 2 to the problem of testing whether an n -vertex biconnected outerplanar DAG admits an upward planar drawing. This constitutes the first barrier to the existence of efficient algorithms for testing the upward planarity of DAGs with no large triconnected minor. We also show a result in the opposite direction. Suppose that partitioning a multiset of positive integers into two multisets so that the sum of the integers in each multiset is n / 2 can be solved in f ( n ) time. Let G be an n -vertex biconnected outerplanar DAG and e be an edge incident to the outer face of an outerplanar drawing of G . Then it can be tested in O ( f ( n ) ) time whether G admits an upward planar drawing with e on the outer face .

The page-number of a directed acyclic graph (a DAG, for short) is the minimum k for which the DAG has a topological order and a k-coloring of its edges such that no two edges of the same color cross, i.e., have alternating endpoints along the topological order. In 1999, Heath and Pemmaraju conjectured that the recognition of DAGs with page-number 2 is NP-complete and proved that recognizing DAGs with page-number 6 is NP-complete (Heath and Pemmaraju (1999) [15]). Binucci et al. recently strengthened this result by proving that recognizing DAGs with page-number k is NP-complete, for every k≥3 (Binucci et al. (2019) [6]). In this paper, we finally resolve Heath and Pemmaraju's conjecture in the affirmative. In particular, our NP-completeness result holds even for st-planar graphs and planar posets.

We obtain new parameterized algorithms for the classical problem of determining whether a directed acyclic graph admits an upward planar drawing. Our results include a new fixed-parameter algorithm parameterized by the number of sources, an XP-algorithm parameterized by treewidth, and a fixed-parameter algorithm parameterized by treedepth. All three algorithms are obtained using a novel framework for the problem that combines SPQR tree-decompositions with parameterized techniques. Our approach unifies and pushes beyond previous tractability results for the problem on series-parallel digraphs, single-source digraphs and outerplanar digraphs.

Given a bipartite graph G = (Vb, Vr, E), the 2-Level Quasi-Planarity problem asks for the existence of a drawing of G in the plane such that the vertices in Vb and in Vr lie along two parallel lines ℓb and ℓr, respectively, each edge in E is drawn in the unbounded strip of the plane delimited by ℓb and ℓr, and no three edges in E pairwise cross. We prove that the 2-LEVEL Quasi-Planarity problem is NP-complete. This answers an open question of Dujmović, Pór, and Wood. Furthermore, we show that the problem becomes linear-time solvable if the ordering of the vertices in Vb along ℓb is prescribed. Our contributions provide the first results on the computational complexity of recognizing quasi-planar graphs, which is a long-standing open question. Our linear-time algorithm exploits several ingredients, including a combinatorial characterization of the positive instances of the problem in terms of the existence of a planar embedding with a caterpillar-like structure, and an SPQR-tree-based algorithm for testing the existence of such a planar embedding. Our algorithm builds upon a classification of the types of embeddings with respect to the structure of the portion of the caterpillar they contain and performs a computation of the realizable embedding types based on a succinct description of their features by means of constant-size gadgets.

In this paper we study the computational complexity of the UPWARD PLANARITY EXTENSION problem, which takes as input an upward planar drawing ΓH of a subgraph H of a directed graph G and asks whether ΓH can be extended to an upward planar drawing of G. Our study fits into the line of research on the extensibility of partial representations, which has recently become a mainstream in Graph Drawing. We show the following results. – First, we prove that the UPWARD PLANARITY EXTENSION problem is NP-complete, even if G has a prescribed upward embedding, the vertex set of H coincides with the one of G, and H contains no edge. – Second, we show that the UPWARD PLANARITY EXTENSION problem can be solved in O(nlog⁡n) time if G is an n-vertex upward planar st-graph. This result improves upon a known O(n2)-time algorithm, which however applies to all n-vertex single-source upward planar graphs. – Finally, we show how to solve in polynomial time a surprisingly difficult version of the UPWARD PLANARITY EXTENSION problem, in which the underlying graph of G is a path or a cycle, G has a prescribed upward embedding, H contains no edges, and no two vertices share the same y-coordinate in ΓH.

We show that if a planar graph G has a plane straight-line drawing in which a subset S of its vertices are collinear, then for any set of points, X, in the plane with |X| = |S|, there is a plane straight-line drawing of G in which the vertices in S are mapped to the points in X. This solves an open problem posed by Ravsky and Verbitsky in 2008. In their terminology, we show that every collinear set is free. This result has applications in graph drawing, including untangling, column planarity, universal point subsets, and partial simultaneous drawings.

A graph drawing is greedy if, for every ordered pair of vertices (x,y), there is a path from x to y such that the Euclidean distance to y decreases monotonically at every vertex of the path. Greedy drawings support a simple geometric routing scheme, in which any node that has to send a packet to a destination "greedily" forwards the packet to any neighbor that is closer to the destination than itself, according to the Euclidean distance in the drawing. In a greedy drawing such a neighbor always exists and hence this routing scheme is guaranteed to succeed. In 2004 Papadimitriou and Ratajczak stated two conjectures related to greedy drawings. The greedy embedding conjecture states that every 3-connected planar graph admits a greedy drawing. The convex greedy embedding conjecture asserts that every 3-connected planar graph admits a planar greedy drawing in which the faces are delimited by convex polygons. In 2008 the greedy embedding conjecture was settled in the positive by Leighton and Moitra. In this paper we prove that every 3-connected planar graph admits a planar greedy drawing. Apart from being a strengthening of Leighton and Moitra's result, this theorem constitutes a natural intermediate step towards a proof of the convex greedy embedding conjecture.

We study a family of algorithms, introduced by Chan [SODA 1999], for drawing ordered rooted binary trees. Any algorithm in this family (which we name an LR-algorithm) takes in input an ordered rooted binary tree T with a root rT, and recursively constructs drawings of the left subtree L of rT and of the right subtree R of rT; then either it applies the left rule, i.e., it places one unit below and to the left of rT, and one unit below with the root of R vertically aligned with rT, or it applies the right rule, i.e., it places one unit below and to the right of rT, and ΓL one unit below with the root of L vertically aligned with rT. In both cases, the edges between rT and its children are represented by straight-line segments. Different LR- algorithms result from different choices on whether the left or right rule is applied at any node of T. We are interested in constructing LR-drawings (that are drawings obtained via LR-algorithms) with small width. Chan showed three LR- algorithms that achieve, for an n-node ordered rooted binary tree, width O(n0.695), width O(n0.5), and width O(n0.48). We prove that, for every n-node ordered rooted binary tree, an LR-drawing with minimum width can be constructed in O(n1.48) time. Further, we show an infinite family of n-node ordered rooted binary trees requiring Ω(n°.418) width in any LR-drawing; no lower bound better than n(log n) was previously known. Finally, we present the results of an experimental evaluation that allowed us to determine the minimum width of all the ordered rooted binary trees with up to 455 nodes. Our interest in LR-drawings is mainly motivated by a result of Di Battista and Frati [Algorithmica 2009], who proved that n-vertex outerplanar graphs have outerplanar straight-line drawings in O(n1.48) area by means of a drawing algorithm which resembles an LR-algorithm. We deepen the connection between LR-drawings and outerplanar drawings by proving that, if n-node ordered rooted binary trees have LR-drawings with f (n) width, for any function f (n), then n-vertex outerplanar graphs have outerplanar straight-line drawings in O(f (n)) area. Finally, we exploit a structural decomposition for ordered rooted binary trees introduced by Chan in order to prove that every n-vertex outerplanar graph has an outer-planar straight-line drawing in area.

Given an $n$-vertex graph and two straight-line planar drawings of the graph that have the same faces and the same outer face, we show that there is a morph (i.e., a continuous transformation) between the two drawings that preserves straight-line planarity and consists of $O(n)$ steps, which we prove is optimal in the worst case. Each step is a unidirectional linear morph, which means that every vertex moves at constant speed along a straight line, and the lines are parallel although the vertex speeds may differ. Thus we provide an efficient version of Cairns' 1944 proof of the existence of straight-line planarity-preserving morphs for triangulated graphs, which required an exponential number of steps.

It is known that every proper minor-closed class of graphs has bounded stack-number (a.k.a. book thickness and page number). While this includes notable graph families such as planar graphs and graphs of bounded genus, many other graph families are not closed under taking minors. For fixed $g$ and $k$, we show that every $n$-vertex graph that can be embedded on a surface of genus $g$ with at most $k$ crossings per edge has stack-number $\mathcal{O}(\log n)$; this includes $k$-planar graphs. The previously best known bound for the stack-number of these families was $\mathcal{O}(\sqrt{n})$, except in the case of $1$-planar graphs. Analogous results are proved for map graphs that can be embedded on a surface of fixed genus. None of these families is closed under taking minors. The main ingredient in the proof of these results is a construction proving that $n$-vertex graphs that admit constant layered separators have $\mathcal{O}(\log n)$ stack-number.

We give an algorithm to compute a morph between any two convex drawings of the same plane graph. The morph preserves the convexity of the drawing at any time instant and moves each vertex along a piecewise linear curve with linear complexity. The linear bound is asymptotically optimal in the worst case.

A simultaneous embedding with fixed edges ( Sefe ) of two planar graphs R and B is a pair of plane drawings of R and B that coincide when restricted to their common vertices and edges. We show that whenever R and B admit a Sefe , they also admit a Sefe in which every edge is a polygonal curve with few bends and every pair of edges has few crossings. Specifically: (1) if R and B are trees then one bend per edge and four crossings per edge pair suffice, (2) if R is a planar graph and B is a tree then six bends per edge and eight crossings per edge pair suffice, and (3) if R and B are planar graphs then six bends per edge and sixteen crossings per edge pair suffice. This improves on results by Grilli et al. (GD’14), who prove that nine bends per edge suffice, and by Chan et al. (GD’14), who prove that twenty-four crossings per edge pair suffice. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Motivated by applications to graph morphing, we consider the following compatible connectivity-augmentation problem: We are given a labelled n-vertex planar graph, G, that has r ≥ 2 connected components, and k ≥ 2 isomorphic planar straight-line drawings, G1, …, G2, of G. We wish to augment G by adding vertices and edges to make it connected in such a way that these vertices and edges can be added to G1, …, G2 as points and straight-line segments, respectively, to obtain k planar straight-line drawings isomorphic to the augmentation of G. We show that adding Θ(nr1–1/k) edges and vertices to G is always sufficient and sometimes necessary to achieve this goal. The upper bound holds for all r ∊ {2, …, n} and k ≥ 2 and is achievable by an algorithm whose running time is O(nr1–1/k) for k = O(1) and whose running time is O(kn2) for general values of k. The lower bound holds for all r ∊ {2, …, n/4} and k ≥ 2.

We study the following problem: given a planar graph G and a planar drawing (embedding) of a subgraph of G , can such a drawing be extended to a planar drawing of the entire graph G ? This problem fits the paradigm of extending a partial solution for a problem to a complete one, which has been studied before in many different settings. Unlike many cases, in which the presence of a partial solution in the input makes an otherwise easy problem hard, we show that the planarity question remains polynomial-time solvable. Our algorithm is based on several combinatorial lemmas, which show that the planarity of partially embedded graphs exhibits the ‘TONCAS’ behavior “the obvious necessary conditions for planarity are also sufficient.” These conditions are expressed in terms of the interplay between (1) the rotation system and containment relationships between cycles and (2) the decomposition of a graph into its connected, biconnected, and triconnected components. This implies that no dynamic programming is needed for a decision algorithm and that the elements of the decomposition can be processed independently. Further, by equipping the components of the decomposition with suitable data structures and by carefully splitting the problem into simpler subproblems, we make our algorithm run in linear time. Finally, we consider several generalizations of the problem, such as minimizing the number of edges of the partial embedding that need to be rerouted to extend it, and argue that they are NP-hard. We also apply our algorithm to the simultaneous graph drawing problem Simultaneous Embedding with Fixed Edges (Sefe) . There we obtain a linear-time algorithm for the case that one of the input graphs or the common graph has a fixed planar embedding.

In 1944, Cairns proved the following theorem: given any two straight-line planar drawings of a triangulation with the same outer face, there exists a morph (i.e., a continuous transformation) between the two drawings so that the drawing remains straight-line planar at all times. Cairns's original proof required exponentially many morphing steps. We prove that there is a morph that consists of O(n2) steps, where each step is a linear morph that moves each vertex at constant speed along a straight line. Using a known result on compatible triangulations this implies that for a general planar graph G and any two straight-line planar drawings of G with the same embedding, there is a morph between the two drawings that preserves straight-line planarity and consists of O(n4) steps.

We prove that planar graphs have $O(\log^2 n)$ queue number, thus improving upon the previous $O(\sqrt n)$ upper bound. Consequently, planar graphs admit three-dimensional straight-line crossing-free grid drawings in $O(n \log^8 n)$ volume, thus improving upon the previous $O(n^{3/2})$ upper bound.

Abstract A greedy drawing is a graph drawing containing a distance‐decreasing path for every pair of nodes. A path ( v 0 , v 1 ,…, v m ) is distance‐decreasing if d ( v i , v m ) < d ( v i ‐1 , v m ), for i = 1,…, m . Greedy drawings easily support geographic greedy routing. Hence, a natural and practical problem is the one of constructing greedy drawings in the plane using few bits for representing vertex Cartesian coordinates and using the Euclidean distance as a metric. We show that there exist greedy‐drawable graphs that do not admit any greedy drawing in which the Cartesian coordinates have less than a polynomial number of bits. © 2012 Wiley Periodicals, Inc. NETWORKS, 2012

We show that every plane graph admits a planar straight-line drawing in which all faces with more than three vertices are nonconvex polygons.

We prove that planar graphs have poly-logarithmic queue number, thus improving upon the previous polynomial upper bound. Consequently, planar graphs admit 3D straight-line crossing-free grid drawings in small volume.

We study the following problem: Given a planar graph G and a planar drawing (embedding) of a subgraph of G, can such a drawing be extended to a planar drawing of the entire graph G? This problem fits the paradigm of extending a partial solution to a complete one, which has been studied before in many different settings. Unlike many cases, in which the presence of a partial solution in the input makes hard an otherwise easy problem, we show that the planarity question remains polynomial-time solvable. Our algorithm is based on several combinatorial lemmata which show that the planarity of partially embedded graphs meets the “on-cas” behaviour – obvious necessary conditions for planarity are also sufficient. These conditions are expressed in terms of the interplay between (a) rotation schemes and containment relationships between cycles and (b) the decomposition of a graph into its connected, biconnected, and triconnected components. This implies that no dynamic programming is needed for a decision algorithm and that the elements of the decomposition can be processed independently. Further, by equipping the components of the decomposition with suitable data structures and by carefully splitting the problem into simpler subproblems, we improve our algorithm to reach linear-time complexity. Finally, we consider several generalizations of the problem, e.g. minimizing the number of edges of the partial embedding that need to be rerouted to extend it, and argue that they are NP-hard. Also, we show how our algorithm can be applied to solve related Graph Drawing problems.