18 citations · 50 across the 37 of their papers we have counts for
24 papers · 1 filter
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 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…
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…
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…
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…
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…
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…
Pole Dancing: 3D Morphs for Tree Drawings
Elena Arseneva, Prosenjit Bose, Pilar Cano +5
We study the question whether a crossing-free 3D morph between two straight-line drawings of an -vertex tree can be constructed consisting of a small number of linear morphing s…
Proceedings of the 25th International Symposium on Graph Drawing and Network Visualization (GD 2017)
Fabrizio Frati, Kwan-Liu Ma
This is the arXiv index for the electronic proceedings of the 25th International Symposium on Graph Drawing and Network Visualization (GD 2017), which was held in Boston, U.S.A., S…
On Planar Greedy Drawings of 3-Connected Planar Graphs
Giordano Da Lozzo, Anthony D'Angelo, Fabrizio Frati
A graph drawing is if, for every ordered pair of vertices , there is a path from to such that the Euclidean distance to decreases monotonically…
LR-Drawings of Ordered Rooted Binary Trees and Near-Linear Area Drawings of Outerplanar Graphs
Fabrizio Frati, Maurizio Patrignani, Vincenzo Roselli
In this paper we study a family of algorithms, introduced by Chan [SODA 1999] and called LR-algorithms, for drawing ordered rooted binary trees. In particular, we are interested in…
Computing NodeTrix Representations of Clustered Graphs
Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati +1
NodeTrix representations are a popular way to visualize clustered graphs; they represent clusters as adjacency matrices and inter-cluster edges as curves connecting the matrix boun…
Stack and Queue Layouts via Layered Separators
Vida Dujmović, Fabrizio Frati
It is known that every proper minor-closed class of graphs has bounded stack-number (a.k.a. book thickness and page number). While this includes notable graph families such as plan…
Drawing Planar Graphs with Many Collinear Vertices
Giordano Da Lozzo, Vida Dujmovic, Fabrizio Frati +2
Consider the following problem: Given a planar graph , what is the maximum number such that has a planar straight-line drawing with collinear vertices? This problem…
How to morph planar graph drawings
Soroush Alamdari, Patrizio Angelini, Fidel Barrera-Cruz +10
Given an -vertex graph and two straight-line planar drawings of the graph that have the same faces and the same outer face, we show that there is a morph (i.e., a continuous tra…
Simultaneous Embeddings with Few Bends and Crossings
Fabrizio Frati, Michael Hoffmann, Vincent Kusters
A simultaneous embedding with fixed edges (SEFE) of two planar graphs and is a pair of plane drawings of and that coincide when restricted to the common vertices an…
A Lower Bound on the Diameter of the Flip Graph
Fabrizio Frati
The flip graph is the graph whose nodes correspond to non-isomorphic combinatorial triangulations and whose edges connect pairs of triangulations that can be obtained one from the…
Optimal Morphs of Convex Drawings
Patrizio Angelini, Giordano Da Lozzo, Fabrizio Frati +3
We give an algorithm to compute a morph between any two convex drawings of the same plane graph. The morph preserves the convexity of the drawing at any time instant and moves each…
Drawing Partially Embedded and Simultaneously Planar Graphs
Timothy M. Chan, Fabrizio Frati, Carsten Gutwenger +3
We investigate the problem of constructing planar drawings with few bends for two related problems, the partially embedded graph problem---to extend a straight-line planar drawing…
A Survey on Small-Area Planar Graph Drawing
Giuseppe Di Battista, Fabrizio Frati
We survey algorithms and bounds for constructing planar drawings of graphs in small area.
Compatible Connectivity-Augmentation of Planar Disconnected Graphs
Greg Aloupis, Luis Barba, Paz Carmi +3
Motivated by applications to graph morphing, we consider the following \emph{compatible connectivity-augmentation problem}: We are given a labelled -vertex planar graph, $\mathc…
Morphing Planar Graphs Drawings Efficiently
Patrizio Angelini, Fabrizio Frati, Maurizio Patrignani +1
A morph between two straight-line planar drawings of the same graph is a continuous transformation from the first to the second drawing such that planarity is preserved at all time…