96 citations · 329 across the 48 of their papers we have counts for
7 papers · 1 filter
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…