Search

Not every directed acyclic graph (DAG) whose underlying undirected graph is planar admits an upward planar drawing. We are interested in pushing the notion of upward drawings beyond planarity by considering upward $k$-planar drawings of DAGs in which the edges are monotonically increasing in a common direction and every edge is crossed at most $k$ times for some integer $k \ge 1$. We show that the number of crossings per edge in a monotone drawing is in general unbounded for the class of bipartite outerplanar, cubic, or bounded pathwidth DAGs. However, it is at most two for outerpaths and it is at most quadratic in the bandwidth in general. From the computational point of view, we prove that upward-$k$-planarity testing is NP-complete already for $k =1$ and even for restricted instances for which upward planarity testing is polynomial. On the positive side, we can decide in linear time whether a single-source DAG admits an upward $1$-planar drawing in which all vertices are incident to the outer face., Comment: This is the extended version, with full appendix, of a paper to appear in the Proc. 32nd Int. Symp. Graph Drawing & Network Visualization (GD 2024)

A RAC graph is one admitting a RAC drawing, that is, a polyline drawing in which each crossing occurs at a right angle. Originally motivated by psychological studies on readability of graph layouts, RAC graphs form one of the most prominent graph classes in beyond planarity. In this work, we study a subclass of RAC graphs, called axis-parallel RAC (or apRAC, for short), that restricts the crossings to pairs of axis-parallel edge-segments. apRAC drawings combine the readability of planar drawings with the clarity of (non-planar) orthogonal drawings. We consider these graphs both with and without bends. Our contribution is as follows: (i) We study inclusion relationships between apRAC and traditional RAC graphs. (ii) We establish bounds on the edge density of apRAC graphs. (iii) We show that every graph with maximum degree 8 is 2-bend apRAC and give a linear time drawing algorithm. Some of our results on apRAC graphs also improve the state of the art for general RAC graphs. We conclude our work with a list of open questions and a discussion of a natural generalization of the apRAC model.

Bipartite graphs model the relationships between two disjoint sets of entities in several applications and are naturally drawn as 2-layer graph drawings. In such drawings, the two sets of entities (vertices) are placed on two parallel lines (layers), and their relationships (edges) are represented by segments connecting vertices. Methods for constructing 2-layer drawings often try to minimize the number of edge crossings. We use vertex splitting to reduce the number of crossings, by replacing selected vertices on one layer by two (or more) copies and suitably distributing their incident edges among these copies. We study several optimization problems related to vertex splitting, either minimizing the number of crossings or removing all crossings with fewest splits. While we prove that some variants are \NP-complete, we obtain polynomial-time algorithms for others. We run our algorithms on a benchmark set of bipartite graphs representing the relationships between human anatomical structures and cell types.

This is the arXiv index for the electronic proceedings of GD 2022, which is held at the Tokyo Institute of Technology, Tokyo, Japan, on September 13 - 16, 2022. It contains the peer-reviewed and revised accepted papers with an optional appendix. Proceedings (without appendices) are also to be published by Springer in the Lecture Notes in Computer Science series.

Motivated by cognitive experiments providing evidence that large crossing-angles do not impair the readability of a graph drawing, RAC (Right Angle Crossing) drawings were introduced to address the problem of producing readable representations of non-planar graphs by supporting the optimal case in which all crossings form 90{\deg} angles. In this work, we make progress on the problem of finding RAC drawings of graphs of low degree. In this context, a long-standing open question asks whether all degree-3 graphs admit straight-line RAC drawings. This question has been positively answered for the Hamiltonian degree-3 graphs. We improve on this result by extending to the class of 3-edge-colorable degree-3 graphs. When each edge is allowed to have one bend, we prove that degree-4 graphs admit such RAC drawings, a result which was previously known only for degree-3 graphs. Finally, we show that 7-edge-colorable degree-7 graphs admit RAC drawings with two bends per edge. This improves over the previous result on degree-6 graphs., Comment: Extended version of a paper presented at MFCS 2022

A map graph is a graph admitting a representation in which vertices are nations on a spherical map and edges are shared curve segments or points between nations. We present an explicit fixed-parameter tractable algorithm for recognizing map graphs parameterized by treewidth. The algorithm has time complexity that is linear in the size of the graph and, if the input is a yes-instance, it reports a certificate in the form of a so-called witness. Furthermore, this result is developed within a more general algorithmic framework that allows to test, for any $k$, if the input graph admits a $k$-map (where at most $k$ nations meet at a common point) or a hole-free~$k$-map (where each point of the sphere is covered by at least one nation). We point out that, although bounding the treewidth of the input graph also bounds the size of its largest clique, the latter alone does not seem to be a strong enough structural limitation to obtain an efficient time complexity. In fact, while the largest clique in a $k$-map graph is $\lfloor 3k/2 \rfloor$, the recognition of $k$-map graphs is still open for any fixed $k \ge 5$.

In an upward-planar L-drawing of a directed acyclic graph (DAG) each edge $e$ is represented as a polyline composed of a vertical segment with its lowest endpoint at the tail of $e$ and of a horizontal segment ending at the head of $e$. Distinct edges may overlap, but not cross. Recently, upward-planar L-drawings have been studied for $st$-graphs, i.e., planar DAGs with a single source $s$ and a single sink $t$ containing an edge directed from $s$ to $t$. It is known that a plane $st$-graph, i.e., an embedded $st$-graph in which the edge $(s,t)$ is incident to the outer face, admits an upward-planar L-drawing if and only if it admits a bitonic $st$-ordering, which can be tested in linear time. We study upward-planar L-drawings of DAGs that are not necessarily $st$-graphs. On the combinatorial side, we show that a plane DAG admits an upward-planar L-drawing if and only if it is a subgraph of a plane $st$-graph admitting a bitonic $st$-ordering. This allows us to show that not every tree with a fixed bimodal embedding admits an upward-planar L-drawing. Moreover, we prove that any acyclic cactus with a single source (or a single sink) admits an upward-planar L-drawing, which respects a given outerplanar embedding if there are no transitive edges. On the algorithmic side, we consider DAGs with a single source (or a single sink). We give linear-time testing algorithms for these DAGs in two cases: (i) when the drawing must respect a prescribed embedding and (ii) when no restriction is given on the embedding, but it is biconnected and series-parallel., Comment: Extended abstract appeared at MFCS 2022

We consider the problem of drawing an outerplanar graph with $n$ vertices with at most one bend per edge if the outer face is already drawn as a simple polygon. We prove that it can be decided in $O(nm)$ time if such a drawing exists, where $m\le n-3$ is the number of interior edges. In the positive case, we can also compute such a drawing., Comment: Appears in the Proceedings of the 29th International Symposium on Graph Drawing and Network Visualization (GD 2021)

Computing a morph between two drawings of a graph is a classical problem in computational geometry and graph drawing. While this problem has been widely studied in the context of planar graphs, very little is known about the existence of topology-preserving morphs for pairs of non-planar graph drawings. We make a step towards this problem by showing that a topology-preserving morph always exists for drawings of a meaningful family of $1$-planar graphs. While our proof is constructive, the vertices may follow trajectories of unbounded complexity., Comment: To appear in Proceedings of the 47th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2021)

Given a bipartite graph $G=(V_b,V_r,E)$, the $2$-Level Quasi-Planarity problem asks for the existence of a drawing of $G$ in the plane such that the vertices in $V_b$ and in $V_r$ lie along two parallel lines $\ell_b$ and $\ell_r$, respectively, each edge in $E$ is drawn in the unbounded strip of the plane delimited by $\ell_b$ and $\ell_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\'c, P\'{o}r, and Wood. Furthermore, we show that the problem becomes linear-time solvable if the ordering of the vertices in $V_b$ along $\ell_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., Comment: Extended version of a paper to appear at SODA '21

A mixed s-stack q-queue layout of a graph consists of a linear order of its vertices and of a partition of its edges into s stacks and q queues, such that no two edges in the same stack cross and no two edges in the same queue nest. In 1992, Heath and Rosenberg conjectured that every planar graph admits a mixed 1-stack 1-queue layout. Recently, Pupyrev disproved this conjectured by demonstrating a planar partial 3-tree that does not admit a 1-stack 1-queue layout. In this note, we strengthen Pupyrev's result by showing that the conjecture does not hold even for 2-trees, also known as series-parallel graphs., Comment: Appears in the Proceedings of the 28th International Symposium on Graph Drawing and Network Visualization (GD 2020)

We study the planar orthogonal drawing style within the framework of partial representation extension. Let $(G,H,{\Gamma}_H )$ be a partial orthogonal drawing, i.e., G is a graph, $H\subseteq G$ is a subgraph and ${\Gamma}_H$ is a planar orthogonal drawing of H. We show that the existence of an orthogonal drawing ${\Gamma}_G$ of $G$ that extends ${\Gamma}_H$ can be tested in linear time. If such a drawing exists, then there also is one that uses $O(|V(H)|)$ bends per edge. On the other hand, we show that it is NP-complete to find an extension that minimizes the number of bends or has a fixed number of bends per edge., Comment: Appears in the Proceedings of the 28th International Symposium on Graph Drawing and Network Visualization (GD 2020)

The $2$-layer drawing model is a well-established paradigm to visualize bipartite graphs. Several beyond-planar graph classes have been studied under this model. Surprisingly, however, the fundamental class of $k$-planar graphs has been considered only for $k=1$ in this context. We provide several contributions that address this gap in the literature. First, we show tight density bounds for the classes of $2$-layer $k$-planar graphs with $k\in\{2,3,4,5\}$. Based on these results, we provide a Crossing Lemma for $2$-layer $k$-planar graphs, which then implies a general density bound for $2$-layer $k$-planar graphs. We prove this bound to be almost optimal with a corresponding lower bound construction. Finally, we study relationships between $k$-planarity and $h$-quasiplanarity in the $2$-layer model and show that $2$-layer $k$-planar graphs have pathwidth at most $k+1$., Comment: Appears in the Proceedings of the 28th International Symposium on Graph Drawing and Network Visualization (GD 2020)

In a planar L-drawing of a directed graph (digraph) each edge e is represented as a polyline composed of a vertical segment starting at the tail of e and a horizontal segment ending at the head of e. Distinct edges may overlap, but not cross. Our main focus is on bimodal graphs, i.e., digraphs admitting a planar embedding in which the incoming and outgoing edges around each vertex are contiguous. We show that every plane bimodal graph without 2-cycles admits a planar L-drawing. This includes the class of upward-plane graphs. Finally, outerplanar digraphs admit a planar L-drawing - although they do not always have a bimodal embedding - but not necessarily with an outerplanar embedding., Comment: Appears in the Proceedings of the 28th International Symposium on Graph Drawing and Network Visualization (GD 2020)

A simple topological graph is $k$-quasiplanar ($k\geq 2$) if it contains no $k$ pairwise crossing edges, and $k$-planar if no edge is crossed more than $k$ times. In this paper, we explore the relationship between $k$-planarity and $k$-quasiplanarity to show that, for $k \geq 2$, every $k$-planar simple topological graph can be transformed into a $(k+1)$-quasiplanar simple topological graph., Comment: arXiv admin note: substantial text overlap with arXiv:1705.05569

We initiate the study of Simultaneous Graph Embedding with Fixed Edges in the beyond planarity framework. In the QuaSEFE problem, we allow edge crossings, as long as each graph individually is drawn quasiplanar, that is, no three edges pairwise cross. We show that a triple consisting of two planar graphs and a tree admit a QuaSEFE. This result also implies that a pair consisting of a 1-planar graph and a planar graph admits a QuaSEFE. We show several other positive results for triples of planar graphs, in which certain structural properties for their common subgraphs are fulfilled. For the case in which simplicity is also required, we give a triple consisting of two quasiplanar graphs and a star that does not admit a QuaSEFE. Moreover, in contrast to the planar SEFE problem, we show that it is not always possible to obtain a QuaSEFE for two matchings if the quasiplanar drawing of one matching is fixed., Comment: Appears in the Proceedings of the 27th International Symposium on Graph Drawing and Network Visualization (GD 2019)

Beyond-planarity focuses on combinatorial properties of classes of non-planar graphs that allow for representations satisfying certain local geometric or topological constraints on their edge crossings. Beside the study of a specific graph class for its maximum edge density, another parameter that is often considered in the literature is the size of the largest complete or complete bipartite graph belonging to it. Overcoming the limitations of standard combinatorial arguments, we present a technique to systematically generate all non-isomorphic topological representations of complete and complete bipartite graphs, taking into account the constraints of the specific class. As a proof of concept, we apply our technique to various beyond-planarity classes and achieve new tight bounds for the aforementioned parameter., Comment: Appears in the Proceedings of the 27th International Symposium on Graph Drawing and Network Visualization (GD 2019)

We consider the problem of morphing between contact representations of a plane graph. In an $\mathcal F$-contact representation of a plane graph $G$, vertices are realized by internally disjoint elements from a family $\mathcal F$ of connected geometric objects. Two such elements touch if and only if their corresponding vertices are adjacent. These touchings also induce the same embedding as in $G$. In a morph between two $\mathcal F$-contact representations we insist that at each time step (continuously throughout the morph) we have an $\mathcal F$-contact representation. We focus on the case when $\mathcal{F}$ is the family of triangles in $\mathbb{R}^2$ that are the lower-right half of axis-parallel rectangles. Such RT-representations exist for every plane graph and right triangles are one of the simplest families of shapes supporting this property. Thus, they provide a natural case to study regarding morphs of contact representations of plane graphs. We study piecewise linear morphs, where each step is a linear morph moving the endpoints of each triangle at constant speed along straight-line trajectories. We provide a polynomial-time algorithm that decides whether there is a piecewise linear morph between two RT-representations of an $n$-vertex plane triangulation, and, if so, computes a morph with $\mathcal O(n^2)$ linear morphs. As a direct consequence, we obtain that for $4$-connected plane triangulations there is a morph between every pair of RT-representations where the ``top-most'' triangle in both representations corresponds to the same vertex. This shows that the realization space of such RT-representations of any $4$-connected plane triangulation forms a connected set., Comment: Extended version of "Morphing Contact Representations of Graphs", to appear in Proceedings of the 35th International Symposium on Computational Geometry (SoCG 2019)

A k-bend right-angle-crossing drawing or (k-bend RAC drawing}, for short) of a graph is a polyline drawing where each edge has at most k bends and the angles formed at the crossing points of the edges are 90 degrees. Accordingly, a graph that admits a k-bend RAC drawing is referred to as k-bend right-angle-crossing graph (or k-bend RAC, for short). In this paper, we continue the study of the maximum edge-density of 1-bend RAC graphs. We show that an n-vertex 1-bend RAC graph cannot have more than $5.5n-O(1)$ edges. We also demonstrate that there exist infinitely many n-vertex 1-bend RAC graphs with exactly $5n-O(1)$ edges. Our results improve both the previously known best upper bound of $6.5n-O(1)$ edges and the corresponding lower bound of $4.5n-O(\sqrt{n})$ edges by Arikushi et al. (Comput. Geom. 45(4), 169--177 (2012))., Comment: Appears in the Proceedings of the 26th International Symposium on Graph Drawing and Network Visualization (GD 2018)

Motivated by hybrid graph representations, we introduce and study the following beyond-planarity problem, which we call $h$-Clique2Path Planarity: Given a graph $G$, whose vertices are partitioned into subsets of size at most $h$, each inducing a clique, remove edges from each clique so that the subgraph induced by each subset is a path, in such a way that the resulting subgraph of $G$ is planar. We study this problem when $G$ is a simple topological graph, and establish its complexity in relation to $k$-planarity. We prove that $h$-Clique2Path Planarity is NP-complete even when $h=4$ and $G$ is a simple $3$-plane graph, while it can be solved in linear time, for any $h$, when $G$ is $1$-plane., Comment: Appears in the Proceedings of the 26th International Symposium on Graph Drawing and Network Visualization (GD 2018)

A drawing of a graph is greedy if for each ordered pair of vertices u and v, there is a path from u to v such that the Euclidean distance to v decreases monotonically at every vertex of the path. The existence of greedy drawings has been widely studied under different topological and geometric constraints, such as planarity, face convexity, and drawing succinctness. We introduce greedy rectilinear drawings, in which each edge is either a horizontal or a vertical segment. These drawings have several properties that improve human readability and support network routing. We address the problem of testing whether a planar rectilinear representation, i.e., a plane graph with specified vertex angles, admits vertex coordinates that define a greedy drawing. We provide a characterization, a linear-time testing algorithm, and a full generative scheme for universal greedy rectilinear representations, i.e., those for which every drawing is greedy. For general greedy rectilinear representations, we give a combinatorial characterization and, based on it, a polynomial-time testing and drawing algorithm for a meaningful subset of instances., Comment: Appears in the Proceedings of the 26th International Symposium on Graph Drawing and Network Visualization (GD 2018)

In the classical Steiner tree problem, given an undirected, connected graph $G=(V,E)$ with non-negative edge costs and a set of \emph{terminals} $T\subseteq V$, the objective is to find a minimum-cost tree $E' \subseteq E$ that spans the terminals. The problem is APX-hard; the best known approximation algorithm has a ratio of $\rho = \ln(4)+\varepsilon < 1.39$. In this paper, we study a natural generalization, the \emph{multi-level Steiner tree} (MLST) problem: given a nested sequence of terminals $T_{\ell} \subset \dots \subset T_1 \subseteq V$, compute nested trees $E_{\ell}\subseteq \dots \subseteq E_1\subseteq E$ that span the corresponding terminal sets with minimum total cost. The MLST problem and variants thereof have been studied under various names including Multi-level Network Design, Quality-of-Service Multicast tree, Grade-of-Service Steiner tree, and Multi-Tier tree. Several approximation results are known. We first present two simple $O(\ell)$-approximation heuristics. Based on these, we introduce a rudimentary composite algorithm that generalizes the above heuristics, and determine its approximation ratio by solving a linear program. We then present a method that guarantees the same approximation ratio using at most $2\ell$ Steiner tree computations. We compare these heuristics experimentally on various instances of up to 500 vertices using three different network generation models. We also present various integer linear programming (ILP) formulations for the MLST problem, and compare their running times on these instances. To our knowledge, the composite algorithm achieves the best approximation ratio for up to $\ell=100$ levels, which is sufficient for most applications such as network visualization or designing multi-level infrastructure., Comment: This paper has been accepted in 17th International Symposium on Experimental Algorithms (SEA 2018)

Beyond-planarity focuses on the study of geometric and topological graphs that are in some sense nearly-planar. Here, planarity is relaxed by allowing edge crossings, but only with respect to some local forbidden crossing configurations. Early research dates back to the 1960s (e.g., Avital and Hanani 1966) for extremal problems on geometric graphs, but is also related to graph drawing problems where visual clutter by edge crossings should be minimized (e.g., Huang et al. 2008) that could negatively affect the readability of the drawing. Different types of forbidden crossing configurations give rise to different families of nearly-planar graphs. Most of the literature focuses on Tur\'an-type problems, which ask for the maximum number of edges a nearly-planar graph can have. Here, we study this problem for bipartite topological graphs, considering several types of nearly-planar graphs, i.e., 1-planar, 2-planar, fan-planar, and RAC graphs. We prove bounds on the number of edges that are tight up to small additive constants; some of them are surprising and not along the lines of the known results for non-bipartite graphs. Our findings lead to an improvement of the leading constant of the well-known Crossing Lemma for bipartite graphs, as well as to a number of interesting research questions on topological graphs.

We initiate the study of the vertex-ply of straight-line drawings, as a relaxation of the recently introduced ply number. Consider the disks centered at each vertex with radius equal to half the length of the longest edge incident to the vertex. The vertex-ply of a drawing is determined by the vertex covered by the maximum number of disks. The main motivation for considering this relaxation is to relate the concept of ply to proximity drawings. In fact, if we interpret the set of disks as proximity regions, a drawing with vertex-ply number 1 can be seen as a weak proximity drawing, which we call empty-ply drawing. We show non-trivial relationships between the ply number and the vertex-ply number. Then, we focus on empty-ply drawings, proving some properties and studying what classes of graphs admit such drawings. Finally, we prove a lower bound on the ply and the vertex-ply of planar drawings., Comment: Appears in the Proceedings of the 25th International Symposium on Graph Drawing and Network Visualization (GD 2017)

We prove that every 1-planar graph G has a z-parallel visibility representation, i.e., a 3D visibility representation in which the vertices are isothetic disjoint rectangles parallel to the xy-plane, and the edges are unobstructed z-parallel visibilities between pairs of rectangles. In addition, the constructed representation is such that there is a plane that intersects all the rectangles, and this intersection defines a bar 1-visibility representation of G., Comment: Appears in the Proceedings of the 25th International Symposium on Graph Drawing and Network Visualization (GD 2017)

In this paper we consider graphs whose edges are associated with a degree of {\em importance}, which may depend on the type of connections they represent or on how recently they appeared in the scene, in a streaming setting. The goal is to construct layouts of these graphs in which the readability of an edge is proportional to its importance, that is, more important edges have fewer crossings. We formalize this problem and study the case in which there exist three different degrees of importance. We give a polynomial-time testing algorithm when the graph induced by the two most important sets of edges is biconnected. We also discuss interesting relationships with other constrained-planarity problems., Comment: Conference version appeared in WG2017

We describe a set of $\Delta -1$ slopes that are universal for 1-bend planar drawings of planar graphs of maximum degree $\Delta \geq 4$; this establishes a new upper bound of $\Delta-1$ on the 1-bend planar slope number. By universal we mean that every planar graph of degree $\Delta$ has a planar drawing with at most one bend per edge and such that the slopes of the segments forming the edges belong to the given set of slopes. This improves over previous results in two ways: Firstly, the best previously known upper bound for the 1-bend planar slope number was $\frac{3}{2} (\Delta -1)$ (the known lower bound being $\frac{3}{4} (\Delta -1)$); secondly, all the known algorithms to construct 1-bend planar drawings with $O(\Delta)$ slopes use a different set of slopes for each graph and can have bad angular resolution, while our algorithm uses a universal set of slopes, which also guarantees that the minimum angle between any two edges incident to a vertex is $\frac{\pi}{(\Delta-1)}$.

A graph is $k$-planar $(k \geq 1)$ if it can be drawn in the plane such that no edge is crossed more than $k$ times. A graph is $k$-quasi planar $(k \geq 2)$ if it can be drawn in the plane with no $k$ pairwise crossing edges. The families of $k$-planar and $k$-quasi planar graphs have been widely studied in the literature, and several bounds have been proven on their edge density. Nonetheless, only trivial results are known about the relationship between these two graph families. In this paper we prove that, for $k \geq 3$, every $k$-planar graph is $(k+1)$-quasi planar., Comment: Superseded by arXiv:1909.00223 as a result of merging with arXiv:1705.05569

Edge bundling is an important concept heavily used for graph visualization purposes. To enable the comparison with other established near-planarity models in graph drawing, we formulate a new edge-bundling model which is inspired by the recently introduced fan-planar graphs. In particular, we restrict the bundling to the end segments of the edges. Similarly to 1-planarity, we call our model 1-fan-bundle-planarity, as we allow at most one crossing per bundle. For the two variants where we allow either one or, more naturally, both end segments of each edge to be part of bundles, we present edge density results and consider various recognition questions, not only for general graphs, but also for the outer and 2-layer variants. We conclude with a series of challenging questions., Comment: Appears in the Proceedings of the 25th International Symposium on Graph Drawing and Network Visualization (GD 2017)

We study the version of the C-Planarity problem in which edges connecting the same pair of clusters must be grouped into pipes, which generalizes the Strip Planarity problem. We give algorithms to decide several families of instances for the two variants in which the order of the pipes around each cluster is given as part of the input or can be chosen by the algorithm., Comment: 19 pages, 9 figures, extended version of the paper appeared at ISAAC 2016

We consider the recently introduced model of \emph{low ply graph drawing}, in which the ply-disks of the vertices do not have many common overlaps, which results in a good distribution of the vertices in the plane. The \emph{ply-disk} of a vertex in a straight-line drawing is the disk centered at it whose radius is half the length of its longest incident edge. The largest number of ply-disks having a common overlap is called the \emph{ply-number} of the drawing. We focus on trees. We first consider drawings of trees with constant ply-number, proving that they may require exponential area, even for stars, and that they may not even exist for bounded-degree trees. Then, we turn our attention to drawings with logarithmic ply-number and show that trees with maximum degree $6$ always admit such drawings in polynomial area., Comment: This is a complete access version of a paper that will appear in the proceedings of GD2016

We introduce and study the $\textit{OrthoSEFE}-k$ problem: Given $k$ planar graphs each with maximum degree 4 and the same vertex set, do they admit an OrthoSEFE, that is, is there an assignment of the vertices to grid points and of the edges to paths on the grid such that the same edges in distinct graphs are assigned the same path and such that the assignment induces a planar orthogonal drawing of each of the $k$ graphs? We show that the problem is NP-complete for $k \geq 3$ even if the shared graph is a Hamiltonian cycle and has sunflower intersection and for $k \geq 2$ even if the shared graph consists of a cycle and of isolated vertices. Whereas the problem is polynomial-time solvable for $k=2$ when the union graph has maximum degree five and the shared graph is biconnected. Further, when the shared graph is biconnected and has sunflower intersection, we show that every positive instance has an OrthoSEFE with at most three bends per edge., Comment: Appears in the Proceedings of the 24th International Symposium on Graph Drawing and Network Visualization (GD 2016)

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., Comment: 31 pages, 18 figures

Defective coloring is a variant of traditional vertex-coloring, according to which adjacent vertices are allowed to have the same color, as long as the monochromatic components induced by the corresponding edges have a certain structure. Due to its important applications, as for example in the bipartisation of graphs, this type of coloring has been extensively studied, mainly with respect to the size, degree, and acyclicity of the monochromatic components. In this paper we focus on defective colorings in which the monochromatic components are acyclic and have small diameter, namely, they form stars. For outerplanar graphs, we give a linear-time algorithm to decide if such a defective coloring exists with two colors and, in the positive case, to construct one. Also, we prove that an outerpath (i.e., an outerplanar graph whose weak-dual is a path) always admits such a two-coloring. Finally, we present NP-completeness results for non-planar and planar graphs of bounded degree for the cases of two and three colors.

In this paper we settle the computational complexity of two open problems related to the extension of the notion of level planarity to surfaces different from the plane. Namely, we show that the problems of testing the existence of a level embedding of a level graph on the surface of the rolling cylinder or on the surface of the torus, respectively known by the name of $\textit{Cyclic Level Planarity}$ and $\textit{Torus Level Planarity}$, are polynomial-time solvable. Moreover, we show a complexity dichotomy for testing the $\textit{Simultaneous Level Planarity}$ of a set of level graphs, with respect to both the number of level graphs and the number of levels., Comment: Appears in the Proceedings of the 24th International Symposium on Graph Drawing and Network Visualization (GD 2016)

Given a planar graph $G$ and a partition of the neighbors of each vertex $v$ in four sets $UR(v)$, $UL(v)$, $DL(v)$, and $DR(v)$, the problem Windrose Planarity asks to decide whether $G$ admits a windrose-planar drawing, that is, a planar drawing in which (i) each neighbor $u \in UR(v)$ is above and to the right of $v$, (ii) each neighbor $u \in UL(v)$ is above and to the left of $v$, (iii) each neighbor $u \in DL(v)$ is below and to the left of $v$, (iv) each neighbor $u \in DR(v)$ is below and to the right of $v$, and (v) edges are represented by curves that are monotone with respect to each axis. By exploiting both the horizontal and the vertical relationship among vertices, windrose-planar drawings allow to simultaneously visualize two partial orders defined by means of the edges of the graph. Although the problem is NP-hard in the general case, we give a polynomial-time algorithm for testing whether there exists a windrose-planar drawing that respects a given combinatorial embedding. This algorithm is based on a characterization of the plane triangulations admitting a windrose-planar drawing. Furthermore, for any embedded graph with $n$ vertices that has a windrose-planar drawing, we can construct one with at most one bend per edge and with at most $2n-5$ bends in total, which lies on the $3n \times 3n$ grid. The latter result contrasts with the fact that straight-line windrose-planar drawings may require exponential area., Comment: Appeared in Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016)

We introduce L-drawings, a novel paradigm for representing directed graphs aiming at combining the readability features of orthogonal drawings with the expressive power of matrix representations. In an L-drawing, vertices have exclusive $x$- and $y$-coordinates and edges consist of two segments, one exiting the source vertically and one entering the destination horizontally. We study the problem of computing L-drawings using minimum ink. We prove its NP-completeness and provide a heuristics based on a polynomial-time algorithm that adds a vertex to a drawing using the minimum additional ink. We performed an experimental analysis of the heuristics which confirms its effectiveness., Comment: 11 pages, 7 figures

We consider drawings of graphs that contain dense subgraphs. We introduce intersection-link representations for such graphs, in which each vertex $u$ is represented by a geometric object $R(u)$ and in which each edge $(u,v)$ is represented by the intersection between $R(u)$ and $R(v)$ if it belongs to a dense subgraph or by a curve connecting the boundaries of $R(u)$ and $R(v)$ otherwise. We study a notion of planarity, called Clique Planarity, for intersection-link representations of graphs in which the dense subgraphs are cliques., Comment: 15 pages, 8 figures, extended version of 'Intersection-Link Representations of Graphs' (23rd International Symposium on Graph Drawing, 2015)

A point set $S \subseteq \mathbb{R}^2$ is universal for a class $\cal G$ if every graph of ${\cal G}$ has a planar straight-line embedding on $S$. It is well-known that the integer grid is a quadratic-size universal point set for planar graphs, while the existence of a sub-quadratic universal point set for them is one of the most fascinating open problems in Graph Drawing. Motivated by the fact that outerplanarity is a key property for the existence of small universal point sets, we study 2-outerplanar graphs and provide for them a universal point set of size $O(n \log n)$., Comment: 23 pages, 11 figures, conference version at GD 2015

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., Comment: To appear in SoCG 2015

In this paper we study two problems related to the drawing of level graphs, that is, T-LEVEL PLANARITY and CLUSTERED-LEVEL PLANARITY. We show that both problems are NP-complete in the general case and that they become polynomial-time solvable when restricted to proper instances., Comment: 10 pages, 4 figures

In this paper we deepen the understanding of the connection between two long-standing Graph Drawing open problems, that is, Simultaneous Embedding with Fixed Edges (SEFE) and Clustered Planarity (C-PLANARITY). In his GD'12 paper Marcus Schaefer presented a reduction from C-PLANARITY to SEFE of two planar graphs (SEFE-2). We prove that a reduction exists also in the opposite direction, if we consider instances of SEFE-2 in which the intersection graph is connected. We pose as an open question whether the two problems are polynomial-time equivalent., Comment: 8 pages, 3 figures, Extended version of 'SEFE = C-Planarity?' (9th International Colloquium on Graph Theory and Combinatorics - ICGT 2014)