Search

The \emph{local edge-length ratio} of a planar straight-line drawing $\Gamma$ is the largest ratio between the lengths of any pair of edges of $\Gamma$ that share a common vertex. The \emph{global edge-length ratio} of $\Gamma$ is the largest ratio between the lengths of any pair of edges of $\Gamma$. The local (global) edge-length ratio of a planar graph is the infimum over all local (global) edge-length ratios of its planar straight-line drawings. We show that there exist planar graphs with $n$ vertices whose local edge-length ratio is $\Omega(\sqrt{n})$. We then show a technique to establish upper bounds on the global (and hence local) edge-length ratio of planar graphs and~apply~it to Halin graphs and to other families of graphs having outerplanarity two.

We study the problem of gradually representing a complex graph as a sequence of drawings of small subgraphs whose union is the complex graph. The sequence of drawings is called \emph{storyplan}, and each drawing in the sequence is called a \emph{frame}. In an outerplanar storyplan, every frame is outerplanar; in a forest storyplan, every frame is acyclic. We identify graph families that admit such storyplans and families for which such storyplans do not always exist. In the affirmative case, we present efficient algorithms that produce straight-line storyplans., Comment: Appears in Proc. SOFSEM 2024

The problem of deciding whether a biconnected planar digraph $G=(V,E)$ can be augmented to become an $st$-planar graph by adding a set of oriented edges $E' \subseteq V \times V$ is known to be NP-complete. We show that the problem is fixed-parameter tractable when parameterized by the size of the set $E'$.

A pair $\langle G_0, G_1 \rangle$ of graphs admits a mutual witness proximity drawing $\langle \Gamma_0, \Gamma_1 \rangle$ when: (i) $\Gamma_i$ represents $G_i$, and (ii) there is an edge $(u,v)$ in $\Gamma_i$ if and only if there is no vertex $w$ in $\Gamma_{1-i}$ that is ``too close'' to both $u$ and $v$ ($i=0,1$). In this paper, we consider infinitely many definitions of closeness by adopting the $\beta$-proximity rule for any $\beta \in [1,\infty]$ and study pairs of isomorphic trees that admit a mutual witness $\beta$-proximity drawing. Specifically, we show that every two isomorphic trees admit a mutual witness $\beta$-proximity drawing for any $\beta \in [1,\infty]$. The constructive technique can be made ``robust'': For some tree pairs we can suitably prune linearly many leaves from one of the two trees and still retain their mutual witness $\beta$-proximity drawability. Notably, in the special case of isomorphic caterpillars and $\beta=1$, we construct linearly separable mutual witness Gabriel drawings., Comment: Appears in the Proceedings of the 31st International Symposium on Graph Drawing and Network Visualization (GD 2023)

Upward planarity testing and Rectilinear planarity testing are central problems in graph drawing. It is known that they are both NP-complete, but XP when parameterized by treewidth. In this paper we show that these two problems are W[1]-hard parameterized by treewidth, which answers open problems posed in two earlier papers. The key step in our proof is an analysis of the All-or-Nothing Flow problem, a generalization of which was used as an intermediate step in the NP-completeness proof for both planarity testing problems. We prove that the flow problem is W[1]-hard parameterized by treewidth on planar graphs, and that the existing chain of reductions to the planarity testing problems can be adapted without blowing up the treewidth. Our reductions also show that the known $n^{O(tw)}$-time algorithms cannot be improved to run in time $n^{o(tw)}$ unless ETH fails., Comment: Appears in the Proceedings of the 31st International Symposium on Graph Drawing and Network Visualization (GD 2023)

Computing planar orthogonal drawings with the minimum number of bends is one of the most relevant topics in Graph Drawing. The problem is known to be NP-hard, even when we want to test the existence of a rectilinear planar drawing, i.e., an orthogonal drawing without bends (Garg and Tamassia, 2001). From the parameterized complexity perspective, the problem is fixed-parameter tractable when parameterized by the sum of three parameters: the number of bends, the number of vertices of degree at most two, and the treewidth of the input graph (Di Giacomo et al., 2022). We improve this last result by showing that the problem remains fixed-parameter tractable when parameterized only by the number of vertices of degree at most two plus the number of bends. As a consequence, rectilinear planarity testing lies in \FPT~parameterized by the number of vertices of degree at most two., Comment: Appears in the Proceedings of the 31st International Symposium on Graph Drawing and Network Visualization (GD 2023)

The study of nonplanar drawings of graphs with restricted crossing configurations is a well-established topic in graph drawing, often referred to as beyond-planar graph drawing. One of the most studied types of drawings in this area are the $k$-planar drawings $(k \geq 1)$, where each edge cannot cross more than $k$ times. We generalize $k$-planar drawings, by introducing the new family of min-$k$-planar drawings. In a min-$k$-planar drawing edges can cross an arbitrary number of times, but for any two crossing edges, one of the two must have no more than $k$ crossings. We prove a general upper bound on the number of edges of min-$k$-planar drawings, a finer upper bound for $k=3$, and tight upper bounds for $k=1,2$. Also, we study the inclusion relations between min-$k$-planar graphs (i.e., graphs admitting min-$k$-planar drawings) and $k$-planar graphs. In our setting we only allow simple drawings, that is, any two edges cross at most once, no two adjacent edges cross, and no three edges intersect at a common crossing point., Comment: Appears in the Proceedings of the 31st International Symposium on Graph Drawing and Network Visualization (GD 2023)

We study the following problem: Given a set $S$ of $n$ points in the plane, how many edge-disjoint plane straight-line spanning paths of $S$ can one draw? A well known result is that when the $n$ points are in convex position, $\lfloor n/2\rfloor$ such paths always exist, but when the points of $S$ are in general position the only known construction gives rise to two edge-disjoint plane straight-line spanning paths. In this paper, we show that for any set $S$ of at least ten points, no three of which are collinear, one can draw at least three edge-disjoint plane straight-line spanning paths of~$S$. Our proof is based on a structural theorem on halving lines of point configurations and a strengthening of the theorem about two spanning paths, which we find interesting in its own right: if $S$ has at least six points, and we prescribe any two points on the boundary of its convex hull, then the set contains two edge-disjoint plane spanning paths starting at the prescribed points., Comment: Appears in the Proceedings of the 31st International Symposium on Graph Drawing and Network Visualization (GD 2023)

Orienting the edges of an undirected graph such that the resulting digraph satisfies some given constraints is a classical problem in graph theory, with multiple algorithmic applications. In particular, an $st$-orientation orients each edge of the input graph such that the resulting digraph is acyclic, and it contains a single source $s$ and a single sink $t$. Computing an $st$-orientation of a graph can be done efficiently, and it finds notable applications in graph algorithms and in particular in graph drawing. On the other hand, finding an $st$-orientation with at most $k$ transitive edges is more challenging and it was recently proven to be NP-hard already when $k=0$. We strengthen this result by showing that the problem remains NP-hard even for graphs of bounded diameter, and for graphs of bounded vertex degree. These computational lower bounds naturally raise the question about which structural parameters can lead to tractable parameterizations of the problem. Our main result is a fixed-parameter tractable algorithm parameterized by treewidth.

This paper studies a \emph{packing} problem in the so-called beyond-planar setting, that is when the host graph is ``almost-planar'' in some sense. Precisely, we consider the case that the host graph is $k$-planar, i.e., it admits an embedding with at most $k$ crossings per edge, and focus on families of $\Delta$-regular caterpillars, that are caterpillars whose non-leaf vertices have the same degree $\Delta$. We study the dependency of $k$ from the number $h$ of caterpillars that are packed, both in the case that these caterpillars are all isomorphic to one another (in which case the packing is called \emph{placement}) and when they are not. We give necessary and sufficient conditions for the placement of $h$ $\Delta$-regular caterpillars and sufficient conditions for the packing of a set of $\Delta_1$-, $\Delta_2$-, $\dots$, $\Delta_h$-regular caterpillars such that the degree $\Delta_i$ and the degree $\Delta_j$ of the non-leaf vertices can differ from one caterpillar to another, for $1 \leq i,j \leq h$, $i\neq j$.

Orthogonal graph drawings are used in applications such as UML diagrams, VLSI layout, cable plans, and metro maps. We focus on drawing planar graphs and assume that we are given an \emph{orthogonal representation} that describes the desired shape, but not the exact coordinates of a drawing. Our aim is to compute an orthogonal drawing on the grid that has minimum area among all grid drawings that adhere to the given orthogonal representation. This problem is called orthogonal compaction (OC) and is known to be NP-hard, even for orthogonal representations of cycles [Evans et al., 2022]. We investigate the complexity of OC with respect to several parameters. Among others, we show that OC is fixed-parameter tractable with respect to the most natural of these parameters, namely, the number of \emph{kitty corners} of the orthogonal representation: the presence of pairs of kitty corners in an orthogonal representation makes the OC problem hard. Informally speaking, a pair of kitty corners is a pair of reflex corners of a face that point at each other. Accordingly, the number of kitty corners is the number of corners that are involved in some pair of kitty corners., Comment: 40 pages, 26 figures, to appear in Proc. SOFSEM 2023

Let $\Gamma$ be a straight-line drawing of a graph and let $u$ and $v$ be two vertices of $\Gamma$. The Gabriel disk of $u,v$ is the disk having $u$ and $v$ as antipodal points. A pair $\langle \Gamma_0,\Gamma_1 \rangle$ of vertex-disjoint straight-line drawings form a mutual witness Gabriel drawing when, for $i=0,1$, any two vertices $u$ and $v$ of $\Gamma_i$ are adjacent if and only if their Gabriel disk does not contain any vertex of $\Gamma_{1-i}$. We characterize the pairs $\langle G_0,G_1 \rangle $ of complete bipartite graphs that admit a mutual witness Gabriel drawing. The characterization leads to a linear time testing algorithm. We also show that when at least one of the graphs in the pair $\langle G_0, G_1 \rangle $ is complete $k$-partite with $k>2$ and all partition sets in the two graphs have size greater than one, the pair does not admit a mutual witness Gabriel drawing., Comment: Appears in the Proceedings of the 30th International Symposium on Graph Drawing and Network Visualization (GD 2022)

Motivated by dynamic graph visualization, we study the problem of representing a graph $G$ in the form of a \emph{storyplan}, that is, a sequence of frames with the following properties. Each frame is a planar drawing of the subgraph of $G$ induced by a suitably defined subset of its vertices. Between two consecutive frames, a new vertex appears while some other vertices may disappear, namely those whose incident edges have already been drawn in at least one frame. In a storyplan, each vertex appears and disappears exactly once. For a vertex (edge) visible in a sequence of consecutive frames, the point (curve) representing it does not change throughout the sequence. Note that the order in which the vertices of $G$ appear in the sequence of frames is a total order. In the \textsc{StoryPlan} problem, we are given a graph and we want to decide whether there exists a total order of its vertices for which a storyplan exists. We prove that the problem is NP-complete, and complement this hardness with two parameterized algorithms, one in the vertex cover number and one in the feedback edge set number of $G$. Also, we prove that partial $3$-trees always admit a storyplan, which can be computed in linear time. Finally, we show that the problem remains NP-complete in the case in which the total order of the vertices is given as part of the input and we have to choose how to draw the frames., Comment: Appears in the Proceedings of the 30th International Symposium on Graph Drawing and Network Visualization (GD 2022)

A graph is rectilinear planar if it admits a planar orthogonal drawing without bends. While testing rectilinear planarity is NP-hard in general (Garg and Tamassia, 2001), it is a long-standing open problem to establish a tight upper bound on its complexity for partial 2-trees, i.e., graphs whose biconnected components are series-parallel. We describe a new O(n^2)-time algorithm to test rectilinear planarity of partial 2-trees, which improves over the current best bound of O(n^3 \log n) (Di Giacomo et al., 2022). Moreover, for partial 2-trees where no two parallel-components in a biconnected component share a pole, we are able to achieve optimal O(n)-time complexity. Our algorithms are based on an extensive study and a deeper understanding of the notion of orthogonal spirality, introduced several years ago (Di Battista et al, 1998) to describe how much an orthogonal drawing of a subgraph is rolled-up in an orthogonal drawing of the graph., Comment: arXiv admin note: substantial text overlap with arXiv:2110.00548 Appears in the Proceedings of the 30th International Symposium on Graph Drawing and Network Visualization (GD 2022)

A planar orthogonal drawing of a planar 4-graph G (i.e., a planar graph with vertex-degree at most four) is a crossing-free drawing that maps each vertex of G to a distinct point of the plane and each edge of $G$ to a sequence of horizontal and vertical segments between its end-points. A longstanding open question in Graph Drawing, dating back over 30 years, is whether there exists a linear-time algorithm to compute an orthogonal drawing of a plane 4-graph with the minimum number of bends. The term "plane" indicates that the input graph comes together with a planar embedding, which must be preserved by the drawing (i.e., the drawing must have the same set of faces as the input graph). In this paper, we positively answer the question above for the widely-studied class of series-parallel graphs. Our linear-time algorithm is based on a characterization of the planar series-parallel graphs that admit an orthogonal drawing without bends. This characterization is given in terms of the orthogonal spirality that each type of triconnected component of the graph can take; the orthogonal spirality of a component measures how much that component is "rolled-up" in an orthogonal drawing of the graph., Comment: arXiv admin note: text overlap with arXiv:2008.03784

We study the long-standing open problem of efficiently testing rectilinear planarity of series-parallel graphs (SP-graphs) in the variable embedding setting. A key ingredient behind the design of a linear-time testing algorithm for SP-graphs of vertex-degree at most three is that one can restrict the attention to a constant number of ``rectilinear shapes'' for each series or parallel component. To formally describe these shapes the notion of spirality can be used. This key ingredient no longer holds for SP-graphs with vertices of degree four, as we prove a logarithmic lower bound on the spirality of their components. The bound holds even for the independent-parallel SP-graphs, in which no two parallel components share a pole. Nonetheless, by studying the spirality properties of the independent-parallel SP-graphs, we are able to design a linear-time rectilinear planarity testing algorithm for this graph family.

This paper studies optimal-area visibility representations of $n$-vertex outer-1-plane graphs, i.e. graphs with a given embedding where all vertices are on the boundary of the outer face and each edge is crossed at most once. We show that any graph of this family admits an embedding-preserving visibility representation whose area is $O(n^{1.5})$ and prove that this area bound is worst-case optimal. We also show that $O(n^{1.48})$ area can be achieved if we represent the vertices as L-shaped orthogonal polygons or if we do not respect the embedding but still have at most one crossing per edge. We also extend the study to other representation models and, among other results, construct asymptotically optimal $O(n\, pw(G))$ area bar-1-visibility representations, where $pw(G)\in O(\log n)$ is the pathwidth of the outer-1-planar graph $G$., Comment: Appears in the Proceedings of the 29th International Symposium on Graph Drawing and Network Visualization (GD 2021)

This paper studies the problem of computing quasi-upward planar drawings of bimodal plane digraphs with minimum curve complexity, i.e., drawings such that the maximum number of bends per edge is minimized. We prove that every bimodal plane digraph admits a quasi-upward planar drawing with curve complexity two, which is worst-case optimal. We also show that the problem of minimizing the curve complexity in a quasi-upward planar drawing can be modeled as a min-cost flow problem on a unit-capacity planar flow network. This gives rise to an $\tilde{O}(m^\frac{4}{3})$-time algorithm that computes a quasi-upward planar drawing with minimum curve complexity; in addition, the drawing has the minimum number of bends when no edge can be bent more than twice. For a contrast, we show bimodal planar digraphs whose bend-minimum quasi-upward planar drawings require linear curve complexity even in the variable embedding setting., Comment: Appears in the Proceedings of the 29th International Symposium on Graph Drawing and Network Visualization (GD 2021)

The $\textit{planar slope number}$ $psn(G)$ of a planar graph $G$ is the minimum number of edge slopes in a planar straight-line drawing of $G$. It is known that $psn(G) \in O(c^\Delta)$ for every planar graph $G$ of degree $\Delta$. This upper bound has been improved to $O(\Delta^5)$ if $G$ has treewidth three, and to $O(\Delta)$ if $G$ has treewidth two. In this paper we prove $psn(G) \in \Theta(\Delta)$ when $G$ is a Halin graph, and thus has treewidth three. Furthermore, we present the first polynomial upper bound on the planar slope number for a family of graphs having treewidth four. Namely we show that $O(\Delta^2)$ slopes suffice for nested pseudotrees., Comment: Extended version of "Planar Drawings with Few Slopes of Halin Graphs and Nested Pseudotrees" to appear in the Proceedings of the 17th Algorithms and Data Structures Symposium (WADS 2021)

The LR-drawing-method is a method of drawing an ordered rooted binary tree based on drawing one root-to-leaf path on a vertical line and attaching recursively obtained drawings of the subtrees on the left and right. In this paper, we study how to generalize this drawing-method to trees of higher arity. We first prove that (with some careful modifications) the proof of existence of a special root-to-leaf path transfers to trees of higher arity. Then we use such paths to obtain generalized LR-drawings of trees of arbitrary arity.

In social networks, individuals' decisions are strongly influenced by recommendations from their friends and acquaintances. The influence maximization (IM) problem asks to select a seed set of users that maximizes the influence spread, i.e., the expected number of users influenced through a stochastic diffusion process triggered by the seeds. In this paper, we present VAIM, a visual analytics system that supports users in analyzing the information diffusion process determined by different IM algorithms. By using VAIM one can: (i) simulate the information spread for a given seed set on a large network, (ii) analyze and compare the effectiveness of different seed sets, and (iii) modify the seed sets to improve the corresponding influence spread., Comment: Appears in the Proceedings of the 28th International Symposium on Graph Drawing and Network Visualization (GD 2020)

Storyline visualizations depict the temporal dynamics of social interactions, as they describe how groups of actors (individuals or organizations) change over time. A common constraint in storyline visualizations is that an actor cannot belong to two different groups at the same time instant. However, this constraint may be too severe in some application scenarios, thus we generalize the model by allowing an actor to simultaneously belong to distinct groups at any point in time. We call this model Storyline with Ubiquitous Actors (SUA). Essential to our model is that an actor is represented as a tree rather than a single line. We describe an algorithmic pipeline to compute storyline visualizations in the SUA model and discuss case studies on publication data., Comment: Appears in the Proceedings of the 28th International Symposium on Graph Drawing and Network Visualization (GD 2020)

A plane graph is rectilinear planar if it admits an embedding-preserving straight-line drawing where each edge is either horizontal or vertical. We prove that rectilinear planarity testing can be solved in optimal $O(n)$ time for any plane series-parallel graph $G$ with $n$ vertices. If $G$ is rectilinear planar, an embedding-preserving rectilinear planar drawing of $G$ can be constructed in $O(n)$ time. Our result is based on a characterization of rectilinear planar series-parallel graphs in terms of intervals of orthogonal spirality that their components can have, and it leads to an algorithm that can be easily implemented., Comment: Appears in the Proceedings of the 28th International Symposium on Graph Drawing and Network Visualization (GD 2020)

We introduce and study the 1-planar packing problem: Given $k$ graphs with $n$ vertices $G_1, \dots, G_k$, find a 1-planar graph that contains the given graphs as edge-disjoint spanning subgraphs. We mainly focus on the case when each $G_i$ is a tree and $k=3$. We prove that a triple consisting of three caterpillars or of two caterpillars and a path may not admit a 1-planar packing, while two paths and a special type of caterpillar always have one. We then study 1-planar packings with few crossings and prove that three paths (resp. cycles) admit a 1-planar packing with at most seven (resp. fourteen) crossings. We finally show that a quadruple consisting of three paths and a perfect matching with $n \geq 12$ vertices admits a 1-planar packing, while such a packing does not exist if $n \leq 10$.

A planar orthogonal drawing $\Gamma$ of a planar graph $G$ is a geometric representation of $G$ such that the vertices are drawn as distinct points of the plane, the edges are drawn as chains of horizontal and vertical segments, and no two edges intersect except at their common end-points. A bend of $\Gamma$ is a point of an edge where a horizontal and a vertical segment meet. $\Gamma$ is bend-minimum if it has the minimum number of bends over all possible planar orthogonal drawings of $G$. This paper addresses a long standing, widely studied, open question: Given a planar 3-graph $G$ (i.e., a planar graph with vertex degree at most three), what is the best computational upper bound to compute a bend-minimum planar orthogonal drawing of $G$ in the variable embedding setting? In this setting the algorithm can choose among the exponentially many planar embeddings of $G$ the one that leads to an orthogonal drawing with the minimum number of bends. We answer the question by describing an $O(n)$-time algorithm that computes a bend-minimum planar orthogonal drawing of $G$ with at most one bend per edge, where $n$ is the number of vertices of $G$. The existence of an orthogonal drawing algorithm that simultaneously minimizes the total number of bends and the number of bends per edge was previously unknown., Comment: 40 pages, 32 figures, full version of SODA 2020 final submission

We study the interplay between embedding constrained planarity and hybrid planarity testing. We consider a constrained planarity testing problem, called 1-Fixed Constrained Planarity, and prove that this problem can be solved in quadratic time for biconnected graphs. Our solution is based on a new definition of fixedness that makes it possible to simplify and extend known techniques about Simultaneous PQ-Ordering. We apply these results to different variants of hybrid planarity testing, including a relaxation of NodeTrix Planarity with fixed sides, that allows rows and columns to be independently permuted.

We study planar straight-line drawings of graphs that minimize the ratio between the length of the longest and the shortest edge. We answer a question of Lazard et al. [Theor. Comput. Sci. 770 (2019), 88--94] and, for any given constant $r$, we provide a $2$-tree which does not admit a planar straight-line drawing with a ratio bounded by $r$. When the ratio is restricted to adjacent edges only, we prove that any $2$-tree admits a planar straight-line drawing whose edge-length ratio is at most $4 + \varepsilon$ for any arbitrarily small $\varepsilon > 0$, hence the upper bound on the local edge-length ratio of partial $2$-trees is $4$., 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)

Given a planar graph $G$ and an integer $b$, OrthogonalPlanarity is the problem of deciding whether $G$ admits an orthogonal drawing with at most $b$ bends in total. We show that OrthogonalPlanarity can be solved in polynomial time if $G$ has bounded treewidth. Our proof is based on an FPT algorithm whose parameters are the number of bends, the treewidth and the number of degree-2 vertices of $G$. This result is based on the concept of sketched orthogonal representation that synthetically describes a family of equivalent orthogonal representations. Our approach can be extended to related problems such as HV-Planarity and FlexDraw. In particular, both OrthogonalPlanarity and HV-Planarity can be decided in $O(n^3 \log n)$ time for series-parallel graphs, which improves over the previously known $O(n^4)$ bounds., Comment: Appears in the Proceedings of the 27th International Symposium on Graph Drawing and Network Visualization (GD 2019)

Hierarchical embedding constraints define a set of allowed cyclic orders for the edges incident to the vertices of a graph. These constraints are expressed in terms of FPQ-trees. FPQ-trees are a variant of PQ-trees that includes F-nodes in addition to P- and to Q-nodes. An F-node represents a permutation that is fixed, i.e., it cannot be reversed. Let $G$ be a graph such that every vertex of $G$ is equipped with a set of FPQ-trees encoding hierarchical embedding constraints for its incident edges. We study the problem of testing whether $G$ admits a planar embedding such that, for each vertex $v$ of $G$, the cyclic order of the edges incident to $v$ is described by at least one of the FPQ-trees associated with~$v$. We prove that the problem is fixed-parameter tractable for biconnected graphs, where the parameters are the treewidth of $G$ and the number of FPQ-trees associated with every vertex of $G$. We also show that the problem is NP-complete if parameterized by the number of FPQ-trees only, and W[1]-hard if parameterized by the treewidth only. Besides being interesting on its own right, the study of planarity testing with hierarchical embedding constraints can be used to address other planarity testing problems. In particular, we apply our techniques to the study of NodeTrix planarity testing of clustered graphs. We show that NodeTrix planarity testing with fixed sides is fixed-parameter tractable when parameterized by the size of the clusters and by the treewidth of the multi-graph obtained by collapsing the clusters to single vertices, provided that this graph is biconnected.

Let $G$ be a simple topological graph and let $\Gamma$ be a polyline drawing of $G$. We say that $\Gamma$ \emph{partially preserves the topology} of $G$ if it has the same external boundary, the same rotation system, and the same set of crossings as $G$. Drawing $\Gamma$ fully preserves the topology of $G$ if the planarization of $G$ and the planarization of $\Gamma$ have the same planar embedding. We show that if the set of crossing-free edges of $G$ forms a connected spanning subgraph, then $G$ admits a polyline drawing that partially preserves its topology and that has curve complexity at most three (i.e., at most three bends per edge). If, however, the set of crossing-free edges of $G$ is not a connected spanning subgraph, the curve complexity may be $\Omega(\sqrt{n})$. Concerning drawings that fully preserve the topology, we show that if $G$ has skewness $k$, it admits one such drawing with curve complexity at most $2k$; for skewness-1 graphs, the curve complexity can be reduced to one, which is a tight bound. We also consider optimal $2$-plane graphs and discuss trade-offs between curve complexity and crossing angle resolution of drawings that fully preserve the topology.

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)

An ortho-polygon visibility representation $\Gamma$ of a $1$-plane graph $G$ (OPVR of $G$) is an embedding preserving drawing that maps each vertex of $G$ to a distinct orthogonal polygon and each edge of $G$ to a vertical or horizontal visibility between its end-vertices. The representation $\Gamma$ has vertex complexity $k$ if every polygon of $\Gamma$ has at most $k$ reflex corners. It is known that $3$-connected $1$-plane graphs admit an OPVR with vertex complexity at most twelve, while vertex complexity at least two may be required in some cases. In this paper, we reduce this gap by showing that vertex complexity five is always sufficient, while vertex complexity four may be required in some cases. These results are based on the study of the combinatorial properties of the B-, T-, and W-configurations in $3$-connected $1$-plane graphs. An implication of the upper bound is the existence of a $\tilde{O}(n^\frac{10}{7})$-time drawing algorithm that computes an OPVR of an $n$-vertex $3$-connected $1$-plane graph on an integer grid of size $O(n) \times O(n)$ and with vertex complexity at most five., Comment: Appears in the Proceedings of the 26th International Symposium on Graph Drawing and Network Visualization (GD 2018)

We present a new model for hybrid planarity that relaxes existing hybrid representations. A graph $G = (V,E)$ is $(k,p)$-planar if $V$ can be partitioned into clusters of size at most $k$ such that $G$ admits a drawing where: (i) each cluster is associated with a closed, bounded planar region, called a cluster region; (ii) cluster regions are pairwise disjoint, (iii) each vertex $v \in V$ is identified with at most $p$ distinct points, called \emph{ports}, on the boundary of its cluster region; (iv) each inter-cluster edge $(u,v) \in E$ is identified with a Jordan arc connecting a port of $u$ to a port of $v$; (v) inter-cluster edges do not cross or intersect cluster regions except at their endpoints. We first tightly bound the number of edges in a $(k,p)$-planar graph with $p

Graph Drawing Beyond Planarity is a rapidly growing research area that classifies and studies geometric representations of non-planar graphs in terms of forbidden crossing configurations. Aim of this survey is to describe the main research directions in this area, the most prominent known results, and some of the most challenging open problems.

Let $G$ be a planar $3$-graph (i.e., a planar graph with vertex degree at most three) with $n$ vertices. We present the first $O(n^2)$-time algorithm that computes a planar orthogonal drawing of $G$ with the minimum number of bends in the variable embedding setting. If either a distinguished edge or a distinguished vertex of $G$ is constrained to be on the external face, a bend-minimum orthogonal drawing of $G$ that respects this constraint can be computed in $O(n)$ time. Different from previous approaches, our algorithm does not use minimum cost flow models and computes drawings where every edge has at most two bends., Comment: Appears in the Proceedings of the 26th International Symposium on Graph Drawing and Network Visualization (GD 2018)

We prove that every set $\mathcal S$ of $\Delta$ slopes containing the horizontal slope is universal for $1$-bend upward planar drawings of bitonic $st$-graphs with maximum vertex degree $\Delta$, i.e., every such digraph admits a $1$-bend upward planar drawing whose edge segments use only slopes in $\mathcal S$. This result is worst-case optimal in terms of the number of slopes, and, for a suitable choice of $\mathcal S$, it gives rise to drawings with worst-case optimal angular resolution. In addition, we prove that every such set $\mathcal S$ can be used to construct $2$-bend upward planar drawings of $n$-vertex planar $st$-graphs with at most $4n-9$ bends in total. Our main tool is a constructive technique that runs in linear time., Comment: Appears in the Proceedings of the 26th International Symposium on Graph Drawing and Network Visualization (GD 2018)

A topological graph is a graph drawn in the plane. A topological graph is $k$-plane, $k>0$, if each edge is crossed at most $k$ times. We study the problem of partitioning the edges of a $k$-plane graph such that each partite set forms a graph with a simpler structure. While this problem has been studied for $k=1$, we focus on optimal $2$-plane and $3$-plane graphs, which are $2$-plane and $3$-plane graphs with maximum density. We prove the following results. (i) It is not possible to partition the edges of a simple optimal $2$-plane graph into a $1$-plane graph and a forest, while (ii) an edge partition formed by a $1$-plane graph and two plane forests always exists and can be computed in linear time. (iii) We describe efficient algorithms to partition the edges of a simple optimal $2$-plane graph into a $1$-plane graph and a plane graph with maximum vertex degree $12$, or with maximum vertex degree $8$ if the optimal $2$-plane graph is such that its crossing-free edges form a graph with no separating triangles. (iv) We exhibit an infinite family of simple optimal $2$-plane graphs such that in any edge partition composed of a $1$-plane graph and a plane graph, the plane graph has maximum vertex degree at least $6$ and the $1$-plane graph has maximum vertex degree at least $12$. (v) We show that every optimal $3$-plane graph whose crossing-free edges form a biconnected graph can be decomposed, in linear time, into a $2$-plane graph and two plane forests.

We show that any outerplanar graph admits a planar straightline drawing such that the length ratio of the longest to the shortest edges is strictly less than 2. This result is tight in the sense that for any $\epsilon > 0$ there are outerplanar graphs that cannot be drawn with an edge-length ratio smaller than $2 - \epsilon$. We also show that every bipartite outerplanar graph has a planar straight-line drawing with edge-length ratio 1, and that, for any $k \geq 1$, there exists an outerplanar graph with a given combinatorial embedding such that any planar straight-line drawing has edge-length ratio greater than k., Comment: Appears in the Proceedings of the 25th International Symposium on Graph Drawing and Network Visualization (GD 2017)

We show that any planar drawing of a forest of three stars whose vertices are constrained to be at fixed vertex locations may require $\Omega(n^\frac{2}{3})$ edges each having $\Omega(n^\frac{1}{3})$ bends in the worst case. The lower bound holds even when the function that maps vertices to points is not a bijection but it is defined by a 3-coloring. In contrast, a constant number of bends per edge can be obtained for 3-colored paths and for 3-colored caterpillars whose leaves all have the same color. Such results answer to a long standing open problem., Comment: Appears in the Proceedings of the 25th International Symposium on Graph Drawing and Network Visualization (GD 2017)

We study the NodeTrix planarity testing problem for flat clustered graphs when the maximum size of each cluster is bounded by a constant $k$. We consider both the case when the sides of the matrices to which the edges are incident are fixed and the case when they can be chosen arbitrarily. We show that NodeTrix planarity testing with fixed sides can be solved in $O(k^{3k+\frac{3}{2}} \cdot n)$ time for every flat clustered graph that can be reduced to a partial 2-tree by collapsing its clusters into single vertices. In the general case, NodeTrix planarity testing with fixed sides can be solved in $O(n)$ time for $k = 2$, but it is NP-complete for any $k > 2$. NodeTrix planarity testing remains NP-complete also in the free sides model when $k > 4$., Comment: Appears in the Proceedings of the 25th International Symposium on Graph Drawing and Network Visualization (GD 2017)

We study straight-line drawings of graphs where the vertices are placed in convex position in the plane, i.e., \emph{convex drawings}. We consider two families of graph classes with convex drawings: \emph{outer $k$-planar} graphs, where each edge is crossed by at most $k$ other edges; and, \emph{outer $k$-quasi-planar} graphs where no $k$ edges can mutually cross. We show that the outer $k$-planar graphs are $\lfloor3.5\sqrt{k}\rfloor$-degenerate, and consequently that every outer $k$-planar graph can be colored with $\lfloor3.5\sqrt{k}\rfloor + 1$ colors. We further show that every outer $k$-planar graph has a balanced vertex separator of size at most $2k+3$. For each fixed $k$, these small balanced separators allow us to test outer $k$-planarity in quasi-polynomial time, e.g., this implies that none of these recognition problems is NP-hard unless the Exponential Time Hypothesis fails. We also show that the class of outer $k$-quasi-planar graphs and the class of planar graphs are incomparable. Finally, we restrict outer $k$-planar and outer $k$-quasi-planar drawings to \emph{full} drawings (where no crossing appears on the boundary of the outer face) and to \emph{closed} drawings (where the vertex sequence on the boundary of the outer face is a Hamiltonian cycle in the graph). For each $k$, we express \emph{closed outer $k$-planarity} and \emph{closed outer $k$-quasi-planarity} in \emph{extended monadic second-order logic}. Due to a result of Wood and Telle (New York J. Math., 2007) every outer $k$-planar graph has treewidth at most $3k+11$. Thus, Courcelle's theorem implies that closed outer $k$-planarity is linear time testable. We leverage this result to further show that full outer $k$-planarity can also be tested in linear time., Comment: Has appeared in the Proceedings of the 25th International Symposium on Graph Drawing and Network Visualization (GD 2017)