AMANDA
Giordano Da Lozzo
Assistant Professor (RTDb)
My research interests are in Algorithm Engineering and Complexity, focused in particular on the theoretical and algorithmic challenges arising from the visualization of graphs.
Publications
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 …
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 …
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 …
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 …
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 …
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 …
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 …
Computing NodeTrix Representations of Clustered Graphs
NodeTrix representations are a popular way to visualize clustered graphs; they represent clusters as adjacency matrices and …
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 …
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}$, …
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 …
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 …
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 …
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 …
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 …
Intersection-Link Representations of Graphs
We consider drawings of graphs that contain dense subgraphs. We introduce intersection-link representations for such graphs, in which …
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 …
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}$, …
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 …
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 …
Computing NodeTrix Representations of Clustered Graphs
NodeTrix representations are a popular way to visualize clustered graphs; they represent clusters as adjacency matrices and …
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 …
L-Drawings of Directed Graphs
We introduce L-drawings, a novel paradigm for representing directed graphs aiming at combining the readability features of orthogonal …
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 …
SEFE = C-Planarity?
In this article, we deepen the understanding of the connection between two long-standing graph drawing open problems, Simultaneous …
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 …
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 …
Intersection-Link Representations of Graphs
We consider drawings of graphs that contain dense subgraphs. We introduce intersection-link representations for such graphs, in which …
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.
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 …
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) …
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 …
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 …
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. …
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) …
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 …
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 …
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 …
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. …
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 …
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 …
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 …
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 …
