Fabrizio Frati

activity

20152022

collaborators

18 papers

cs.CG2022

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…

cs.DS2021

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 $G = (V, E, λ)$ be a weighted planar graph, where $λ : E \to R^{+}$ is a length function.…

cs.DS2020

2-Level Quasi-Planarity or How Caterpillars Climb (SPQR-)Trees

Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista +2

Given a bipartite graph $G = (V_{b}, V_{r}, E)$ , the $2$ -Level Quasi-Planarity problem asks for the existence of a drawing of $G$ in the plane such that the vertices in $V_{b}$ and in $V_{r}$ …

cs.DS2020

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…

math.CO2020

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…

cs.DS2020

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…