Search

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 $\Theta(\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., Comment: Appears in the Proceedings of the 32nd International Symposium on Graph Drawing and Network Visualization (GD 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'$.

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)

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.

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.

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)

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 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.

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

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 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 the following problem: Given $k$ paths that share the same vertex set, is there a simultaneous geometric embedding of these paths such that each individual drawing is monotone in some direction? We prove that for any dimension $d \geq 2$, there is a set of $d+1$ paths that does not admit a monotone simultaneous geometric embedding.

We consider the problem of placing arrow heads in directed graph drawings without them overlapping other drawn objects. This gives drawings where edge directions can be deduced unambiguously. We show hardness of the problem, present exact and heuristic algorithms, and report on a practical study., Comment: Appears in the Proceedings of the 24th International Symposium on Graph Drawing and Network Visualization (GD 2016)

In this paper we study the problem of designing a distributed graph visualization algorithm for large graphs. The algorithm must be simple to implement and the computing infrastructure must not require major hardware or software investments. We design, implement, and experiment a force-directed algorithm in Giraph, a popular open source framework for distributed computing, based on a vertex-centric design paradigm. The algorithm is tested both on real and artificial graphs with up to million edges, by using a rather inexpensive PaaS (Platform as a Service) infrastructure of Amazon. The experiments show the scalability and effectiveness of our technique when compared to a centralized implementation of the same force-directed model. We show that graphs with about one million edges can be drawn in less than 8 minutes, by spending about 1\$ per drawing in the cloud computing infrastructure.

A graph is called a strong (resp. weak) bar 1-visibility graph if its vertices can be represented as horizontal segments (bars) in the plane so that its edges are all (resp. a subset of) the pairs of vertices whose bars have a $\epsilon$-thick vertical line connecting them that intersects at most one other bar. We explore the relation among weak (resp. strong) bar 1-visibility graphs and other nearly planar graph classes. In particular, we study their relation to 1-planar graphs, which have a drawing with at most one crossing per edge; quasi-planar graphs, which have a drawing with no three mutually crossing edges; the squares of planar 1-flow networks, which are upward digraphs with in- or out-degree at most one. Our main results are that 1-planar graphs and the (undirected) squares of planar 1-flow networks are weak bar 1-visibility graphs and that these are quasi-planar graphs.

It is proven that every set $S$ of distinct points in the plane with cardinality $\lceil \frac{\sqrt{\log_2 n}-1}{4} \rceil$ can be a subset of the vertices of a crossing-free straight-line drawing of any planar graph with $n$ vertices. It is also proven that if $S$ is restricted to be a one-sided convex point set, its cardinality increases to $\lceil \sqrt[3]{n} \rceil$. The proofs are constructive and give rise to O(n)-time drawing algorithms. As a part of our proofs, we show that every maximal planar graph contains a large induced biconnected outerplanar graphs and a large induced outerpath (an outerplanar graph whose weak dual is a path).

A drawing of a given (abstract) tree that is a minimum spanning tree of the vertex set is considered aesthetically pleasing. However, such a drawing can only exist if the tree has maximum degree at most 6. What can be said for trees of higher degree? We approach this question by supposing that a partition or covering of the tree by subtrees of bounded degree is given. Then we show that if the partition or covering satisfies some natural properties, then there is a drawing of the entire tree such that each of the given subtrees is drawn as a minimum spanning tree of its vertex set.