96 citations · 329 across the 48 of their papers we have counts for
64 papers
How Close is a Tree to a Euclidean Minimum Spanning Tree?
Todor Antić, Jiří Fiala, Jelena Glišić +8
Let be a straight-line crossing-free drawing of a tree . A \emph{bad pair} in is a pair of non-adjacent vertices of whose Euclidean distance in is smaller than t…
Optimal Orthogonal Drawings in Linear Time
Walter Didimo, Giuseppe Liotta, Giacomo Ortali +1
A planar orthogonal drawing Γ of a connected 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…
New Bounds on the Local and Global Edge-length Ratio of Planar Graphs
Emilio Di Giacomo, Walter Didimo, Giuseppe Liotta +3
The \emph{local edge-length ratio} of a planar straight-line drawing is the largest ratio between the lengths of any pair of edges of that share a common vertex. The \emph{…
On the Parameterized Complexity of Bend-Minimum Orthogonal Planarity
Emilio Di Giacomo, Walter Didimo, Giuseppe Liotta +2
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…
Upward and Orthogonal Planarity are W[1]-hard Parameterized by Treewidth
Bart M. P. Jansen, Liana Khazaliya, Philipp Kindermann +3
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…
Min--planar Drawings of Graphs
Carla Binucci, Aaron Büngener, Giuseppe Di Battista +7
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. On…
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…
Three Edge-disjoint Plane Spanning Paths in a Point Set
Philipp Kindermann, Jan Kratochvíl, Giuseppe Liotta +1
We consider the following problem: Given a set of distinct points in the plane, how many edge-disjoint plane straight-line spanning paths can be drawn on ? Each spanning…
-planar Placement and Packing of -regular Caterpillars
Carla Binucci, Emilio Di Giacomo, Michael Kaufmann +2
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…
Parameterized Approaches to Orthogonal Compaction
Walter Didimo, Siddharth Gupta, Philipp Kindermann +3
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…
On the Complexity of the Storyplan Problem
Carla Binucci, Emilio Di Giacomo, William J. Lenhart +4
Motivated by dynamic graph visualization, we study the problem of representing a graph in the form of a \emph{storyplan}, that is, a sequence of frames with the following prope…
Mutual Witness Gabriel Drawings of Complete Bipartite Graphs
William J. Lenhart, Giuseppe Liotta
Let be a straight-line drawing of a graph and let and be two vertices of . The Gabriel disk of is the disk having and as antipodal points. A pair $\lan…
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…
Computing Bend-Minimum Orthogonal Drawings of Plane Series-Parallel Graphs in Linear Time
Walter Didimo, Michael Kaufmann, Giuseppe Liotta +1
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 o…
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…
Quasi-upward Planar Drawings with Minimum Curve Complexity
Carla Binucci, Emilio Di Giacomo, Giuseppe Liotta +1
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 ben…
Optimal-area visibility representations of outer-1-plane graphs
Therese Biedl, Giuseppe Liotta, Jayson Lynch +1
This paper studies optimal-area visibility representations of -vertex outer-1-plane graphs, i.e. graphs with a given embedding where all vertices are on the boundary of the oute…
Generalized LR-drawings of trees
Therese Biedl, Giuseppe Liotta, Jayson Lynch +1
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…
Planar Drawings with Few Slopes of Halin Graphs and Nested Pseudotrees
Steven Chaplick, Giordano Da Lozzo, Emilio Di Giacomo +2
The of a planar graph is the minimum number of edge slopes in a planar straight-line drawing of . It is known that $psn(G) \in O(c^Δ)…
VAIM: Visual Analytics for Influence Maximization
Alessio Arleo, Walter Didimo, Giuseppe Liotta +2
In social networks, individuals' decisions are strongly influenced by recommendations from their friends and acquaintances. The influence maximization (IM) problem asks to select a…
Storyline Visualizations with Ubiquitous Actors
Emilio Di Giacomo, Walter Didimo, Giuseppe Liotta +2
Storyline visualizations depict the temporal dynamics of social interactions, as they describe how groups of actors (individuals or organizations) change over time. A common constr…
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…
Packing Trees into 1-planar Graphs
Felice De Luca, Emilio Di Giacomo, Seok-Hee Hong +6
We introduce and study the 1-planar packing problem: Given graphs with vertices , find a 1-planar graph that contains the given graphs as edge-disjoint spa…
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…