18 citations · 50 across the 37 of their papers we have counts for
50 papers
Extending Biconnected Straight-Line Planar Drawings
Giordano Andreola, Susanna Caroppo, Giordano Da Lozzo +5
The Partial Drawing Extensibility problem, for short PDE, takes as input a triple , where is a planar graph, is a subgraph of , and is a st…
On Large Induced Outerplanar Subgraphs in -Outerplanar Graphs
Marco D'Elia, Fabrizio Frati
Borradaile, Le and Sherman-Bennett [Graphs and Combinatorics, 2017] proved that every -vertex -outerplane graph has a set of at least vertices that induces an outerpla…
On Planar Straight-Line Dominance Drawings
Patrizio Angelini, Michael A. Bekos, Giuseppe Di Battista +3
We study the following question, which has been considered since the 90's: Does every -planar graph admit a planar straight-line dominance drawing? We show concrete evidence fo…
Upward Pointset Embeddings of Planar st-Graphs
Carlos Alegria, Susanna Caroppo, Giordano Da Lozzo +5
We study upward pointset embeddings (UPSEs) of planar -graphs. Let be a planar -graph and let be a pointset with . An UPSE of …
Efficient Enumeration of Drawings and Combinatorial Structures for Maximal Planar Graphs
Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati +2
We propose efficient algorithms for enumerating the notorious combinatorial structures of maximal planar graphs, called canonical orderings and Schnyder woods, and the related clas…
Upward Planarity Testing of Biconnected Outerplanar DAGs Solves Partition
Fabrizio Frati
We show an -time reduction from the problem of testing whether a multiset of positive integers can be partitioned into two multisets so that the sum of the integers in each m…
Morphing Planar Graph Drawings Through 3D
Kevin Buchin, Will Evans, Fabrizio Frati +4
In this paper, we investigate crossing-free 3D morphs between planar straight-line drawings. We show that, for any two (not necessarily topologically equivalent) planar straight-li…
Testing Upward Planarity of Partial -Trees
Steven Chaplick, Emilio Di Giacomo, Fabrizio Frati +3
We present an -time algorithm to test whether an -vertex directed partial -tree is upward planar. This result improves upon the previously best known algorithm, which…
Unit-length Rectangular Drawings of Graphs
Carlos Alegria, Giordano Da Lozzo, Giuseppe Di Battista +3
A rectangular drawing of a planar graph is a planar drawing of in which vertices are mapped to grid points, edges are mapped to horizontal and vertical straight-line segmen…
Recognizing DAGs with Page-Number 2 is NP-complete
Michael A. Bekos, Giordano Da Lozzo, Fabrizio Frati +3
The page-number of a directed acyclic graph (a DAG, for short) is the minimum for which the DAG has a topological order and a -coloring of its edges such that no two edges o…
Parameterized Algorithms for Upward Planarity
Steven Chaplick, Emilio Di Giacomo, Fabrizio Frati +3
We obtain new parameterized algorithms for the classical problem of determining whether a directed acyclic graph admits an upward planar drawing. Our results include a new fixed-pa…
Planar Straight-line Realizations of 2-Trees with Prescribed Edge Lengths
Carlos Alegría, Manuel Borrazzo, Giordano Da Lozzo +3
We study a classic problem introduced thirty years ago by Eades and Wormald. Let be a weighted planar graph, where is a length function.…
From Tutte to Floater and Gotsman: On the Resolution of Planar Straight-line Drawings and Morphs
Giuseppe Di Battista, Fabrizio Frati
The algorithm of Tutte for constructing convex planar straight-line drawings and the algorithm of Floater and Gotsman for constructing planar straight-line morphs are among the mos…
2-Level Quasi-Planarity or How Caterpillars Climb (SPQR-)Trees
Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista +2
Given a bipartite graph , the -Level Quasi-Planarity problem asks for the existence of a drawing of in the plane such that the vertices in and in …
Schematic Representation of Large Biconnected Graphs
Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani +1
Suppose that a biconnected graph is given, consisting of a large component plus several other smaller components, each separated from the main component by a separation pair. We in…
Universal Geometric Graphs
Fabrizio Frati, Michael Hoffmann, Csaba D. Tóth
We introduce and study the problem of constructing geometric graphs that have few vertices and edges and that are universal for planar graphs or for some sub-class of planar graphs…
Planar Rectilinear Drawings of Outerplanar Graphs in Linear Time
Fabrizio Frati
We show how to test in linear time whether an outerplanar graph admits a planar rectilinear drawing, both if the graph has a prescribed plane embedding that the drawing has to resp…
On the Area Requirements of Planar Greedy Drawings of Triconnected Planar Graphs
Giordano Da Lozzo, Anthony D'Angelo, Fabrizio Frati
In this paper we study the area requirements of planar greedy drawings of triconnected planar graphs. Cao, Strelzoff, and Sun exhibited a family of subdivisions of triconn…
Drawing Graphs as Spanners
Oswin Aichholzer, Manuel Borrazzo, Prosenjit Bose +4
We study the problem of embedding graphs in the plane as good geometric spanners. That is, for a graph , the goal is to construct a straight-line drawing of in the plane…
How to Morph a Tree on a Small Grid
Fidel Barrera-Cruz, Manuel Borrazzo, Giordano Da Lozzo +4
In this paper we study planar morphs between straight-line planar grid drawings of trees. A morph consists of a sequence of morphing steps, where in a morphing step vertices move a…
Graph Stories in Small Area
Manuel Borrazzo, Giordano Da Lozzo, Giuseppe Di Battista +2
We study the problem of drawing a dynamic graph, where each vertex appears in the graph at a certain time and remains in the graph for a fixed amount of time, called the window siz…
On the Planar Edge-Length Ratio of Planar Graphs
Manuel Borrazzo, Fabrizio Frati
The edge-length ratio of a straight-line drawing of a graph is the ratio between the lengths of the longest and of the shortest edge in the drawing. The planar edge-length ratio of…
On the Area Requirements of Planar Straight-Line Orthogonal Drawings of Ternary Trees
Barbara Covella, Fabrizio Frati, Maurizio Patrignani
In this paper, we study the area requirements of planar straight-line orthogonal drawings of ternary trees. We prove that every ternary tree admits such a drawing in sub-quadratic…
Extending Upward Planar Graph Drawings
Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati
In this paper we study the computational complexity of the Upward Planarity Extension problem, which takes in input an upward planar drawing of a subgraph of a directed g…