Giordano Da Lozzo is a postdoctoral researcher in the Department of Engineering at the Roma Tre University, mentored by Giuseppe Di Battista. Until October 2017, he was an assistant project scientist at the CECS Department of The Donald Bren School of Information & Computer Sciences at University of California, Irvine, jointly mentored by Michael T. Goodrich and David A. Eppstein. Until September 2016, he was a postdoctoral fellow at the Department of Informatics and Automation (DIA) of the Roma Tre University, mentored by Giuseppe Di Battista.
His research interests are in the areas of graph theory, algorithms, and complexity theory, with a particular focus on problems in Graph Drawing, Computational Geometry, and Combinatorial Optimization. He received the “Laurea” Bachelor degree and the “Laurea Magistrale” Master degree in Computer Science and Engineering at the Roma Tre University, and defended his Ph.D. thesis at the Department of Informatics and Automation (DIA) of the same institution, jointly advised by Giuseppe Di Battista and Maurizio Patrignani, on June 2015.
PhD in Computer Science and Automation Engineering, 2015
Roma Tre University
MEng in Computer Science (110/110 cum laude), 2010
Roma Tre University
Efficient Algorithms for HArnessing networked Data (funded by the Italian Ministry of University and Scientific Research)
MOrphing graph Drawings Efficiently (funded by the Italian Ministry of University and Scientific Research)
The Space/Time Analysis for Cybersecurity program (funded by the U.S. Defense Advanced Research Projects Agency)
Algorithmics for MAssive and Networked DAta (funded by the Italian Ministry of University and Scientific Research)
Here are some of the courses for which I was formally appointed as the main teacher:
Here are some of the courses for which I was formally appointed as a teaching assistant:
Program committee memberships:
WADS 2021: 16th International Symposium on Algorithms and Data Structures
GD 2019: 27th International Symposium on Graph Drawing and Network Visualization
GD 2017: 25th International Symposium on Graph Drawing and Network Visualization
Giordano Da Lozzo, David Eppstein, Michael T. Goodrich, Siddharth Gupta: C-Planarity Testing of Embedded Clustered Graphs with Bounded Dual Carving-Width. IPEC 2019: 9:1-9:17 PDF
Patrizio Angelini, Giordano Da Lozzo, Marco Di Bartolomeo, Valentino Di Donato, Maurizio Patrignani, Vincenzo Roselli, Ioannis G. Tollis: L-Drawings of Directed Graphs. SOFSEM 2016: 134-147 PDF
Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani, Ignaz Rutter: On the Relationship Between Map Graphs and Clique Planar Graphs. Graph Drawing 2015: 548-550 PDF
Giordano Da Lozzo: Design and analysis of a paradigm for visualizing and exploring relational data in a mobile environment and its implementation on the Google Android platform. Roma Tre University. 2011.
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 an assignment of its edges to the pages of the book, so that no two edges on the same page cross. The book thickness of a graph is the minimum number of pages over all its book embeddings. For planar graphs, a fundamental result is due to Yannakakis, who proposed an algorithm to compute embeddings of planar graphs in books with four pages. Our main contribution is a technique that generalizes this result to a much wider family of nonplanar graphs, which is characterized by a biconnected skeleton of crossing-free edges whose faces have bounded degree. Notably, this family includes all 1-planar and all optimal 2-planar graphs as subgraphs. We prove that this family of graphs has bounded book thickness, and as a corollary, we obtain the first constant upper bound for the book thickness of optimal 2-planar graphs.
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 incident to at most $k$ pairs of consecutive edges with opposite orientations, i.e., the incoming and the outgoing edges at each vertex are grouped by the embedding into at most $k$ sets of consecutive edges with the same orientation. In this paper, we study the $k$-Modality problem, which asks for the existence of a $k$-modal embedding of a planar digraph. This combinatorial problem is at the very core of a variety of constrained embedding questions for planar digraphs and flat clustered networks.
First, since the $2$-Modality problem can be easily solved in linear time, we consider the general $k$-Modality problem for any value of $k>2$ and show that the problem is NP-complete for planar digraphs of maximum degree $\Delta \geq k+3$. We relate its computational complexity to that of two notions of planarity for flat clustered networks$:$ Planar Intersection-Link and Planar NodeTrix representations. This allows us to answer in the strongest possible way an open question by Di Giacomo et al. GD17, concerning the complexity of constructing planar NodeTrix representations of flat clustered networks with small clusters, and to address a research question by Angelini et al. JGAA17, concerning intersection-link representations based on geometric objects that determine complex arrangements. On the positive side, we provide a simple FPT algorithm for partial $2$-trees of arbitrary degree, whose running time is exponential in $k$ and linear in the input size.
Second, motivated by the recently-introduced planar L-drawings of planar digraphs GD17, which require the computation of a $4$-modal embedding, we focus our attention on $k=4$. On the algorithmic side, we show a complexity dichotomy for the $4$-Modality problem with respect to $\Delta$, by providing a linear-time algorithm for planar digraphs with $\Delta \leq 6$. This algorithmic result is based on decomposing the input digraph into its blocks via BC-trees and each of these blocks into its triconnected components via SPQR-trees. In particular, we are able to show that the constraints imposed on the embedding by the rigid triconnected components can be tackled by means of a small set of reduction rules and discover that the algorithmic core of the problem lies in special instances of NaeSat, which we prove to be always NAE-satisfiable–a result of independent interest that improves on Porschen et al. SAT03.
Finally, on the combinatorial side, we consider outerplanar digraphs and show that any such a digraph always admits a $k$-modal embedding with $k=4$ and that this value of $k$ is best possible for the digraphs in this family.