GIORDANO DA LOZZO
GIORDANO DA LOZZO
Home
Projects
Teaching
EDs, PCs & Workshops
University Service
Keynotes
Awards
Featured
Publications
Contact
Publications
Type
Conference paper
Journal article
Thesis
Date
2020
2019
2018
2017
2016
2015
2014
2013
2012
2010
Upward Planar Morphs
We prove that, given two topologically equivalent upward planar straight-line drawings of an $n$-vertex directed graph $G$, there …
Giordano Da Lozzo
,
Giuseppe Di Battista
,
Fabrizio Frati
,
Maurizio Patrignani
,
Vincenzo Roselli
Cite
Project
Slides
DOI
GD 2018
Algorithmica
ArXiv
Simple k-planar graphs are simple (k + 1)-quasiplanar
A simple topological graph is $k$-quasiplanar ($k\geq 2$) if it contains no $k$ pairwise crossing edges, and $k$-planar if no edge is …
Patrizio Angelini
,
Michael Bekos
,
Giordano Da Lozzo
,
Franz Brandenburg
,
Giuseppe Di Battista
,
Walter Didimo
,
Michael Hoffmann
,
Giuseppe Liotta
,
Fabrizio Montecchiani
,
Ignaz Rutter
,
Csaba D.Tóthgh
Cite
Project
DOI
WG 2017
EuroCG 2017
J. Comb. Theory, Series B
ArXiv
On Planar Greedy Drawings of 3-Connected Planar Graphs
A graph drawing is
greedy
if, for every ordered pair of vertices $(x,y)$, there is a path from $x$ to $y$ such that the Euclidean …
Giordano Da Lozzo
,
Anthony D’Angelo
,
Fabrizio Frati
Cite
Project
DOI
SoCG 2017
Discrete & Comput. Geometry
ArXiv
Extending Upward Planar Graph Drawings
In this paper we study the computational complexity of the
Upward Planarity Extension
problem, which takes in input an upward planar …
Giordano Da Lozzo
,
Giuseppe Di Battista
,
Fabrizio Frati
Cite
Project
DOI
WADS 2019
Comp. Geometry
ArXiv
Book Embeddings of Nonplanar Graphs with Small Faces in Few Pages
An embedding of a graph in a book, called
book embedding
, consists of a linear ordering of its vertices along the spine of the book and …
Michael Bekos
,
Giordano Da Lozzo
,
Svenja Griesbach
,
Martin Gronemann
,
Fabrizio Montecchiani
,
Chrysanthi Raftopoulou
Cite
Project
SoCG 2020
ArXiv
Beyond level planarity: Cyclic, torus, and simultaneous level planarity
In this paper we settle the computational complexity of two open problems related to the extension of the notion of level planarity to …
Giordano Da Lozzo
,
Giuseppe Di Battista
,
Fabrizio Frati
,
Maurizio Patrignani
,
Ignaz Rutter
Cite
Project
Slides
DOI
GD 2016
Ther. Comp. Science
ArXiv
Graph Stories in Small Area
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 …
Manuel Borrazzo
,
Giordano Da Lozzo
,
Giuseppe Di Battista
,
Fabrizio Frati
,
Maurizio Patrignani
Cite
Project
Slides
DOI
GD 2019
ArXiv
Computing k-Modal Embeddings of Planar Digraphs
Given a planar digraph $G$ and a positive even integer $k$, an embedding of $G$ in the plane is
$k$-modal
, if every vertex of $G$ is …
Juan Jose Besa
,
Giordano Da Lozzo
,
Michael Goodrich
Cite
Project
DOI
ESA 2019
ArXiv
Reaching 3-Connectivity via Edge-edge Additions
Given a graph $G$ and a pair $\langle e’,e’’\rangle$ of distinct edges of $G$, an
edge-edge addition on $\langle …
Giordano Da Lozzo
,
Ignaz Rutter
Cite
Project
Slides
DOI
IWOCA 2019
ArXiv
Upward Book Embeddings of st-Graphs
We study
k-page upward book embeddings
($k$UBEs) of $st$-graphs, that is, book embeddings of single-source single-sink directed acyclic …
Carla Binucci
,
Giordano Da Lozzo
,
Emilio Di Giacomo
,
Walter Didimo
,
Tamara Mchedlidze
,
Maurizio Patrignani
PDF
Cite
Project
DOI
SoCG 2019
ArXiv
Morphing Contact Representations of Graphs
We consider the problem of morphing between contact representations of a plane graph. In a contact representation of a plane graph, …
Patrizio Angelini
,
Steven Chaplick
,
Sabine Cornelsen
,
Giordano Da Lozzo
,
Vincenzo Roselli
PDF
Cite
Project
DOI
SoCG 2019
ArXiv
How to Morph a Tree on a Small Grid
In this paper, we study planar morphs between straight-line planar grid drawings of trees. A morph consists of a sequence of morphing …
Fidel Barrera-Cruz
,
Manuel Borrazzo
,
Giordano Da Lozzo
,
Giuseppe Di Battista
,
Fabrizio Frati
,
Maurizio Patrignani
,
Vincenzo Roselli
Cite
Project
DOI
WADS 2019
ArXiv
Extending Upward Planar Graph Drawings
In this paper we study the computational complexity of the
Upward Planarity Extension
problem, which takes in input an upward planar …
Giordano Da Lozzo
,
Giuseppe Di Battista
,
Fabrizio Frati
Cite
Project
DOI
WADS 2019
Comp. Geometry
ArXiv
Planarity of Streamed Graphs
In this research we introduce a notion of planarity for graphs that are presented in a streaming fashion. A
streamed graph
is a stream …
Giordano Da Lozzo
,
Ignaz Rutter
Cite
Project
Slides
DOI
CIAC 2015
Theor. Comp. Science
ArXiv
Clustered Planarity with Pipes
In this paper we study the version of the
C-Planarity
problem in which edges connecting the same pair of clusters must be grouped into …
Giordano Da Lozzo
,
Patrizio Angelini
Cite
Project
DOI
ISAAC 2016
Algorithmica
ArXiv
C-Planarity Testing of Embedded Clustered Graphs with Bounded Dual Carving-Width
For a
clustered graph
, i.e, a graph whose vertex set is recursively partitioned into clusters, the C-Planarity Testing problem asks …
Giordano Da Lozzo
,
David Eppstein
,
Michael Goodrich
,
Siddharth Gupta
PDF
Cite
Project
DOI
IPEC 2019
ArXiv
Analogies between the Crossing Number and the Tangle Crossing Number
Tanglegrams are special graphs that consist of a pair of rooted binary trees with the same number of leaves, and a perfect matching …
Robin Anderson
,
Shuliang Bai
,
Fidel Barrera-Cruz
,
Éva Czabarka
,
Giordano Da Lozzo
,
Natalie Hobson
,
Jephian C.-H. Lin
,
Austin Mohr
,
Heather Smith
,
László A. Székely
,
Hays Whitlatch
Cite
EJC 2018
JMM18
ArXiv
3-coloring arrangements of line segments with 4 slopes is hard
In a paper first appeared at
SODA ’04
, Eppstein proved that testing the $3$-colorability of arrangements of line segments is an …
Patrizio Angelini
,
Giordano Da Lozzo
Cite
IPL 2018
Upward Planar Morphs
We prove that, given two topologically equivalent upward planar straight-line drawings of an $n$-vertex directed graph $G$, there …
Giordano Da Lozzo
,
Giuseppe Di Battista
,
Fabrizio Frati
,
Maurizio Patrignani
,
Vincenzo Roselli
Cite
Project
Slides
DOI
GD 2018
Algorithmica
ArXiv
Subexponential-Time and FPT Algorithms for Embedded Flat Clustered Planarity
The C-Planarity problem asks for a drawing of a
clustered graph
, i.e., a graph whose vertices belong to properly nested clusters, in …
Giordano Da Lozzo
,
David Eppstein
,
Michael Goodrich
,
Siddharth Gupta
Cite
Project
DOI
WG 2018
ArXiv
Blog
Approximation Algorithms for Facial Cycles in Planar Embeddings
Consider the following combinatorial problem$:$ Given a planar graph $G$ and a set of simple cycles $\mathcal C$ in $G$, find a planar …
Giordano Da Lozzo
,
Ignaz Rutter
Cite
Project
Slides
DOI
ISAAC 2018
Windrose Planarity: Embedding Graphs with Direction-Constrained Edges
Given a planar graph $G(V,E)$ and a partition of the neighbors of each vertex $v \in V$ in four sets $\overset{\nwarrow}{v}$, …
Patrizio Angelini
,
Giordano Da Lozzo
,
Giuseppe Di Battista
,
Valentino Di Donato
,
Philipp Kindermann
,
Günter Rote
,
Ignaz Rutter
Cite
Project
DOI
SODA 2016
ACM Trans. Alg.
ArXiv
Drawing Planar Graphs with Many Collinear Vertices
Consider the following problem$:$ Given a planar graph $G$, what is the maximum number $p$ such that $G$ has a planar straight-line …
Giordano Da Lozzo
,
Vida Dujmovic
,
Fabrizio Frati
,
Tamara Mchedlidze
,
Vincenzo Roselli
Cite
Project
DOI
GD 2016
JoCG
ArXiv
Computing NodeTrix Representations of Clustered Graphs
NodeTrix representations are a popular way to visualize clustered graphs; they represent clusters as adjacency matrices and …
Giordano Da Lozzo
,
Giuseppe Di Battista
,
Fabrizio Frati
,
Maurizio Patrignani
Cite
Project
DOI
GD 2016
JGAA
ArXiv
WebApp
Algorithms and Bounds for L-Drawings of Directed Graphs
We introduce
L-drawings
, a novel paradigm for representing directed graphs aiming at combining the readability features of orthogonal …
Patrizio Angelini
,
Giordano Da Lozzo
,
Marco Di Bartolomeo
,
Valentino Di Donato
,
Maurizio Patrignani
,
Vincenzo Roselli
,
Ioannis Tollis
Cite
Project
DOI
SOFSEM 2016
Int. J. Found. Comput. Sci.
ArXiv
On Planar Greedy Drawings of 3-Connected Planar Graphs
A graph drawing is
greedy
if, for every ordered pair of vertices $(x,y)$, there is a path from $x$ to $y$ such that the Euclidean …
Giordano Da Lozzo
,
Anthony D’Angelo
,
Fabrizio Frati
Cite
Project
DOI
SoCG 2017
Discrete & Comput. Geometry
ArXiv
How to Morph Planar Graph Drawings
Given an $n$-vertex graph and two straight-line planar drawings of the graph that have the same faces and the same outer face, we show …
Soroush Alamdari
,
Patrizio Angelini
,
Fidel Barrera-Cruz
,
Timothy Chan
,
Giordano Da Lozzo
,
Giuseppe Di Battista
,
Fabrizio Frati
,
Penny Haxell
,
Anna Lubiw
,
Maurizio Patrignani
,
Vincenzo Roselli
,
Sahil Singla
,
Bryan T. Wilkinson
Cite
Project
DOI
SIAM J. Comp.
ArXiv
Planar L-Drawings of Directed Graphs
We study planar drawings of directed graphs in the L-drawing standard. We provide necessary conditions for the existence of these …
Steven Chaplick
,
Markus Chimani
,
Sabine Cornelsen
,
Giordano Da Lozzo
,
Martin Nöllenburg
,
Maurizio Patrignani
,
Ioannis G. Tollis
,
Alexander Wolff
Cite
Project
DOI
GD 2017
ArXiv
On the Relationship Between k-Planar and k-Quasi-Planar Graphs
A simple topological graph is $k$-quasiplanar ($k\geq 2$) if it contains no $k$ pairwise crossing edges, and $k$-planar if no edge is …
Patrizio Angelini
,
Michael Bekos
,
Giordano Da Lozzo
,
Franz Brandenburg
,
Giuseppe Di Battista
,
Walter Didimo
,
Giuseppe Liotta
,
Fabrizio Montecchiani
,
Ignaz Rutter
Cite
Project
DOI
WG 2017
EuroCG 2017
J. Comb. Theory, Series B
ArXiv
Square-Contact Representations of Partial 2-Trees and Triconnected Simply-Nested Graphs
A
square-contact representation
of a planar graph $G=(V,E)$ maps the vertices in $V$ to interior disjoint axis-aligned squares in the …
Giordano Da Lozzo
,
William E. Devanny
,
David Eppstein
,
Timothy Johnson
Cite
Project
DOI
ISAAC 2017
Blog
ArXiv
Strip Planarity Testing for Embedded Planar Graphs
In this paper we introduce and study the
Strip Planarity Testing
problem, which takes as an input a planar graph $G(V,E)$ and a …
Patrizio Angelini
,
Giordano Da Lozzo
,
Giuseppe Di Battista
,
Fabrizio Frati
Cite
Project
DOI
GD 2013
Algorithmica
ArXiv
Intersection-Link Representations of Graphs
We consider drawings of graphs that contain dense subgraphs. We introduce
intersection-link representations
for such graphs, in which …
Patrizio Angelini
,
Giordano Da Lozzo
,
Giuseppe Di Battista
,
Fabrizio Frati
,
Maurizio Patrignani
,
Ignaz Rutter
Cite
Project
Slides
DOI
GD 2015
JGAA
ArXiv
Windrose Planarity: Embedding Graphs with Direction-Constrained Edges
Given a planar graph $G(V,E)$ and a partition of the neighbors of each vertex $v \in V$ in four sets $\overset{\nwarrow}{v}$, …
Patrizio Angelini
,
Giordano Da Lozzo
,
Giuseppe Di Battista
,
Valentino Di Donato
,
Philipp Kindermann
,
Günter Rote
,
Ignaz Rutter
Cite
Project
DOI
SODA 2016
ACM Trans. Alg.
ArXiv
Simultaneous Orthogonal Planarity
We introduce and study the OrthoSEFE-$k$ problem$:$ Given~$k$ planar graphs each with maximum degree 4 and the same vertex set, is …
Patrizio Angelini
,
Steven Chaplick
,
Sabine Cornelsen
,
Giordano Da Lozzo
,
Giuseppe Di Battista
,
Peter Eades
,
Philipp Kindermann
,
Jan Kratochvíl
,
Fabian Lipp
,
Ignaz Rutter
Cite
Project
DOI
GD 2016
ArXiv
L-Drawings of Directed Graphs
We introduce
L-drawings
, a novel paradigm for representing directed graphs aiming at combining the readability features of orthogonal …
Patrizio Angelini
,
Giordano Da Lozzo
,
Marco Di Bartolomeo
,
Valentino Di Donato
,
Maurizio Patrignani
,
Vincenzo Roselli
,
Ioannis Tollis
Cite
Project
DOI
SOFSEM 2016
Int. J. Found. Comput. Sci.
ArXiv
Drawing Planar Graphs with Many Collinear Vertices
Consider the following problem$:$ Given a planar graph $G$, what is the maximum number $p$ such that $G$ has a planar straight-line …
Giordano Da Lozzo
,
Vida Dujmovic
,
Fabrizio Frati
,
Tamara Mchedlidze
,
Vincenzo Roselli
Cite
Project
DOI
GD 2016
JoCG
ArXiv
Computing NodeTrix Representations of Clustered Graphs
NodeTrix representations are a popular way to visualize clustered graphs; they represent clusters as adjacency matrices and …
Giordano Da Lozzo
,
Giuseppe Di Battista
,
Fabrizio Frati
,
Maurizio Patrignani
Cite
Project
DOI
GD 2016
JGAA
ArXiv
WebApp
Clustered Planarity with Pipes
In this paper we study the version of the
C-Planarity
problem in which edges connecting the same pair of clusters must be grouped into …
Giordano Da Lozzo
,
Patrizio Angelini
Cite
Project
DOI
ISAAC 2016
Algorithmica
ArXiv
Beyond Level Planarity
In this paper we settle the computational complexity of two open problems related to the extension of the notion of level planarity to …
Giordano Da Lozzo
,
Giuseppe Di Battista
,
Fabrizio Frati
,
Maurizio Patrignani
,
Ignaz Rutter
Cite
Project
Slides
DOI
GD 2016
Ther. Comp. Science
ArXiv
SEFE = C-Planarity?
In this article, we deepen the understanding of the connection between two long-standing graph drawing open problems, Simultaneous …
Patrizio Angelini
,
Giordano Da Lozzo
Cite
Project
DOI
ICGT 2014
Comp. J.
ArXiv
Optimal Morphs of Convex Drawings
We give an algorithm to compute a morph between any two convex drawings of the same plane graph. The morph preserves the convexity of …
Patrizio Angelini
,
Giordano Da Lozzo
,
Fabrizio Frati
,
Anna Lubiw
,
Maurizio Patrignani
,
Vincenzo Roselli
PDF
Cite
Project
DOI
SoCG 2015
ArXiv
Planar Graphs with Vertices in Prescribed Regions: models, algorithms, and complexity
The volume and the complexity of structured relational information created and handled by modern information systems has drastically …
Giordano Da Lozzo
PDF
Cite
Planarity of Streamed Graphs
In this research we introduce a notion of planarity for graphs that are presented in a streaming fashion. A
streamed graph
is a stream …
Giordano Da Lozzo
,
Ignaz Rutter
Cite
Project
Slides
DOI
CIAC 2015
Theor. Comp. Science
ArXiv
On the Relationship Between Map Graphs and Clique Planar Graphs
In this poster we establish that neither of the classes of map graphs and of clique planar graphs is contained in the other.
Patrizio Angelini
,
Giordano Da Lozzo
,
Giuseppe Di Battista
,
Fabrizio Frati
,
Maurizio Patrignani
,
Ignaz Rutter
Cite
Project
Poster
Slides
DOI
GD 2015
JGAA
ArXiv
Intersection-Link Representations of Graphs
We consider drawings of graphs that contain dense subgraphs. We introduce
intersection-link representations
for such graphs, in which …
Patrizio Angelini
,
Giordano Da Lozzo
,
Giuseppe Di Battista
,
Fabrizio Frati
,
Maurizio Patrignani
,
Ignaz Rutter
Cite
Project
Slides
DOI
GD 2015
JGAA
ArXiv
Drawing Georeferenced Graphs - Combining Graph Drawing and Geographic Data
We consider the task of visually exploring relationships (such as established connections, similarity, reachability, etc) among a set …
Giordano Da Lozzo
,
Marco Di Bartolomeo
,
Maurizio Patrignani
,
Giuseppe Di Battista
,
Davide Cannone
,
Sergio Tortora
Cite
Project
DOI
IVAPP 2015
The Importance of Being Proper - (In Clustered-Level Planarity and T-Level Planarity)
In this paper we study two problems related to the drawing of level graphs, that is,
$T$-Level Planarity
and
Clustered-Level Planarity
. …
Patrizio Angelini
,
Giordano Da Lozzo
,
Giuseppe Di Battista
,
Maurizio Patrignani
,
Fabrizio Frati
,
Vincenzo Roselli
Cite
Project
Slides
DOI
GD 2014
Theor. Comp. Science
ArXiv
Relaxing the constraints of clustered planarity
In a drawing of a clustered graph vertices and edges are drawn as points and curves, respectively, while clusters are represented by …
Patrizio Angelini
,
Giordano Da Lozzo
,
Giuseppe Di Battista
,
Fabrizio Frati
,
Maurizio Patrignani
,
Vincenzo Roselli
Cite
Project
DOI
Comp. Geometry
ArXiv
Algorithms and bounds for drawing non-planar graphs with crossing-free subgraphs
We initiate the study of the following problem$:$
Given a non-planar graph $G$ and a planar subgraph $S$ of $G$, does there exist a …
Patrizio Angelini
,
Carla Binucci
,
Giordano Da Lozzo
,
Walter Didimo
,
Luca Grilli
,
Fabrizio Montecchiani
,
Maurizio Patrignani
,
Ioannis Tollis
Cite
Project
Slides
DOI
GD 2013
Comp. Geometry
ArXiv
Advancements on SEFE and Partitioned Book Embedding problems
In this work we investigate the complexity of some combinatorial problems related to the
Simultaneous Embedding with Fixed Edges
(SEFE) …
Patrizio Angelini
,
Giordano Da Lozzo
,
Daniel Neuwirth
Cite
Project
DOI
WALCOM 2014
Theor. Comp. Science
ArXiv
On Some NP-complete SEFE Problems
In this work we investigate the complexity of some combinatorial problems related to the
Simultaneous Embedding with Fixed Edges
(SEFE) …
Patrizio Angelini
,
Giordano Da Lozzo
,
Daniel Neuwirth
Cite
Project
DOI
WALCOM 2014
Theor. Comp. Science
ArXiv
Morphing Planar Graph Drawings Optimally
We provide an algorithm for computing a planar morph between any two planar straight-line drawings of any $n$-vertex plane graph in …
Patrizio Angelini
,
Giordano Da Lozzo
,
Giuseppe Di Battista
,
Fabrizio Frati
,
Maurizio Patrignani
,
Vincenzo Roselli
Cite
Project
DOI
ICALP 2014
SIAM J. Comp.
ArXiv
The Importance of Being Proper - (In Clustered-Level Planarity and T-Level Planarity)
In this paper we study two problems related to the drawing of level graphs, that is,
$T$-Level Planarity
and
Clustered-Level Planarity
. …
Patrizio Angelini
,
Giordano Da Lozzo
,
Giuseppe Di Battista
,
Maurizio Patrignani
,
Fabrizio Frati
,
Vincenzo Roselli
Cite
Project
Slides
DOI
GD 2014
Theor. Comp. Science
ArXiv
Planar Embeddings with Small and Uniform Faces
Motivated by finding planar embeddings that lead to drawings with favorable aesthetics, we study the problems MINMAXFACE and …
Giordano Da Lozzo
,
Vít Jelínek
,
Jan Kratochvíl
,
Ignaz Rutter
Cite
Project
Slides
DOI
ISAAC 2014
ArXiv
Anchored Drawings of Planar Graphs
In this paper we study the
ANCHORED GRAPH DRAWING
(AGD) problem$:$ Given a planar graph $G$, an initial placement for its vertices, and …
Patrizio Angelini
,
Giordano Da Lozzo
,
Marco Di Bartolomeo
,
Giuseppe Di Battista
,
Seok-Hee Hong
,
Maurizio Patrignani
,
Vincenzo Roselli
Cite
Project
Slides
DOI
GD 2014
Visual discovery of the correlation between BGP routing and round-trip delay active measurements
Inter-domain routing data and Internet active probing measurements are two types of information commonly available in huge datasets and …
Giordano Da Lozzo
,
Giuseppe Di Battista
,
Claudio Squarcella
Cite
Code
Project
Poster
Video
DOI
WIV 2012
Computing
WEB
Strip Planarity Testing
In this paper we introduce and study the
strip planarity testing
problem, which takes as an input a planar graph $G(V,E)$ and a …
Patrizio Angelini
,
Giordano Da Lozzo
,
Giuseppe Di Battista
,
Fabrizio Frati
Cite
Project
DOI
GD 2013
Algorithmica
ArXiv
Drawing Non-Planar Graphs with Crossing-Free Subgraphs
We initiate the study of the following problem$:$
Given a non-planar graph $G$ and a planar subgraph $S$ of $G$, does there exist a …
Patrizio Angelini
,
Carla Binucci
,
Giordano Da Lozzo
,
Walter Didimo
,
Luca Grilli
,
Fabrizio Montecchiani
,
Maurizio Patrignani
,
Ioannis Tollis
Cite
Project
Slides
DOI
GD 2013
Comp. Geometry
ArXiv
Drawing Graphs on a Smartphone
We present a system for the visualization of information modeled in terms of a graph on a smartphone. First, we show the adopted …
Giordano Da Lozzo
,
Giuseppe Di Battista
,
Francesco Ingrassia
Cite
Project
Video
DOI
GD 2010
JGAA
Drawing Graphs on a Smartphone
We present a system for the visualization of information modeled in terms of a graph on a smartphone. First, we show the adopted …
Giordano Da Lozzo
,
Giuseppe Di Battista
,
Francesco Ingrassia
PDF
Cite
Project
Video
DOI
GD 2010
JGAA
Cite
×