96 citations · 329 across the 48 of their papers we have counts for
15 papers · 1 filter
On the Parameterized Complexity of Computing -Orientations with Few Transitive Edges
Carla Binucci, Giuseppe Liotta, Fabrizio Montecchiani +2
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 applic…
Rectilinear Planarity of Partial 2-Trees
Walter Didimo, Michael Kaufmann, Giuseppe Liotta +1
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 l…
Spirality and Rectilinear Planarity Testing of Independent-Parallel SP-Graphs
Walter Didimo, Michael Kaufmann, Giuseppe Liotta +1
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 behin…
Rectilinear Planarity Testing of Plane Series-Parallel Graphs in Linear Time
Walter Didimo, Michael Kaufmann, Giuseppe Liotta +1
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…
Optimal Orthogonal Drawings of Planar 3-Graphs in Linear Time
Walter Didimo, Giuseppe Liotta, Giacomo Ortali +1
A planar orthogonal drawing of a planar graph is a geometric representation of such that the vertices are drawn as distinct points of the plane, the edges are drawn as…
Simultaneous FPQ-Ordering and Hybrid Planarity Testing
Giuseppe Liotta, Ignaz Rutter, Alessandra Tappini
We study the interplay between embedding constrained planarity and hybrid planarity testing. We consider a constrained planarity testing problem, called 1-Fixed Constrained Planari…
The QuaSEFE Problem
Patrizio Angelini, Henry Förster, Michael Hoffmann +4
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 ind…
Graph Planarity Testing with Hierarchical Embedding Constraints
Giuseppe Liotta, Ignaz Rutter, Alessandra Tappini
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. F…
Turning Cliques into Paths to Achieve Planarity
Patrizio Angelini, Peter Eades, Seok-Hee Hong +5
Motivated by hybrid graph representations, we introduce and study the following beyond-planarity problem, which we call -Clique2Path Planarity: Given a graph , whose vertices…
Ortho-polygon Visibility Representations of 3-connected 1-plane Graphs
Giuseppe Liotta, Fabrizio Montecchiani, Alessandra Tappini
An ortho-polygon visibility representation of a -plane graph (OPVR of ) is an embedding preserving drawing that maps each vertex of to a distinct orthogonal polyg…
(k,p)-Planarity: A Relaxation of Hybrid Planarity
Emilio Di Giacomo, William J. Lenhart, Giuseppe Liotta +2
We present a new model for hybrid planarity that relaxes existing hybrid representations. A graph is -planar if can be partitioned into clusters of size at m…
Bend-minimum Orthogonal Drawings in Quadratic Time
Walter Didimo, Giuseppe Liotta, Maurizio Patrignani
Let be a planar -graph (i.e., a planar graph with vertex degree at most three) with vertices. We present the first -time algorithm that computes a planar orthogo…
NodeTrix Planarity Testing with Small Clusters
Emilio Di Giacomo, Giuseppe Liotta, Maurizio Patrignani +2
We study the NodeTrix planarity testing problem for flat clustered graphs when the maximum size of each cluster is bounded by a constant . We consider both the case when the sid…
Placing Arrows in Directed Graph Drawings
Carla Binucci, Markus Chimani, Walter Didimo +2
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 una…
A Distributed Force-Directed Algorithm on Giraph: Design and Experiments
Alessio Arleo, Walter Didimo, Giuseppe Liotta +1
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 infrastruc…