Source author record

Giordano Da Lozzo

Giordano Da Lozzo appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Catalog footprint

What is connected

29works
5topics
4close collaborators

Actions

Connect this record

Log in to claim

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

29 published item(s)

preprint2022arXiv

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 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, all optimal 2-planar, and all k-map (with bounded k) 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 and k-map graphs.

preprint2022arXiv

Graph Product Structure for h-Framed Graphs

Graph product structure theory expresses certain graphs as subgraphs of the strong product of much simpler graphs. In particular, an elegant formulation for the corresponding structural theorems involves the strong product of a path and of a bounded treewidth graph, and allows to lift combinatorial results for bounded treewidth graphs to graph classes for which the product structure holds, such as to planar graphs [Dujmović et al., J. ACM, 67(4), 22:1-38, 2020]. In this paper, we join the search for extensions of this powerful tool beyond planarity by considering the h-framed graphs, a graph class that includes 1-planar, optimal 2-planar, and k-map graphs (for appropriate values of h). We establish a graph product structure theorem for h-framed graphs stating that the graphs in this class are subgraphs of the strong product of a path, of a planar graph of treewidth at most 3, and of a clique of size $3\lfloor h/2 \rfloor +\lfloor h/3 \rfloor -1$. This allows us to improve over the previous structural theorems for 1-planar and k-map graphs. Our results constitute significant progress over the previous bounds on the queue number, non-repetitive chromatic number, and p-centered chromatic number of these graph classes, e.g., we lower the currently best upper bound on the queue number of 1-planar graphs and k-map graphs from 495 to 81 and from 32225k(k-3) to 61k, respectively. We also employ the product structure machinery to improve the current upper bounds of twin-width of planar and 1-planar graphs from 183 to 37, and from O(1) to 80, respectively. All our structural results are constructive and yield efficient algorithms to obtain the corresponding decompositions.

preprint2022arXiv

On Upward-Planar L-Drawings of Graphs

In an upward-planar L-drawing of a directed acyclic graph (DAG) each edge $e$ is represented as a polyline composed of a vertical segment with its lowest endpoint at the tail of $e$ and of a horizontal segment ending at the head of $e$. Distinct edges may overlap, but not cross. Recently, upward-planar L-drawings have been studied for $st$-graphs, i.e., planar DAGs with a single source $s$ and a single sink $t$ containing an edge directed from $s$ to $t$. It is known that a plane $st$-graph, i.e., an embedded $st$-graph in which the edge $(s,t)$ is incident to the outer face, admits an upward-planar L-drawing if and only if it admits a bitonic $st$-ordering, which can be tested in linear time. We study upward-planar L-drawings of DAGs that are not necessarily $st$-graphs. On the combinatorial side, we show that a plane DAG admits an upward-planar L-drawing if and only if it is a subgraph of a plane $st$-graph admitting a bitonic $st$-ordering. This allows us to show that not every tree with a fixed bimodal embedding admits an upward-planar L-drawing. Moreover, we prove that any acyclic cactus with a single source (or a single sink) admits an upward-planar L-drawing, which respects a given outerplanar embedding if there are no transitive edges. On the algorithmic side, we consider DAGs with a single source (or a single sink). We give linear-time testing algorithms for these DAGs in two cases: (i) when the drawing must respect a prescribed embedding and (ii) when no restriction is given on the embedding, but it is biconnected and series-parallel.

preprint2022arXiv

Recognizing Map Graphs of Bounded Treewidth

A map graph is a graph admitting a representation in which vertices are nations on a spherical map and edges are shared curve segments or points between nations. We present an explicit fixed-parameter tractable algorithm for recognizing map graphs parameterized by treewidth. The algorithm has time complexity that is linear in the size of the graph and, if the input is a yes-instance, it reports a certificate in the form of a so-called witness. Furthermore, this result is developed within a more general algorithmic framework that allows to test, for any $k$, if the input graph admits a $k$-map (where at most $k$ nations meet at a common point) or a hole-free~$k$-map (where each point of the sphere is covered by at least one nation). We point out that, although bounding the treewidth of the input graph also bounds the size of its largest clique, the latter alone does not seem to be a strong enough structural limitation to obtain an efficient time complexity. In fact, while the largest clique in a $k$-map graph is $\lfloor 3k/2 \rfloor$, the recognition of $k$-map graphs is still open for any fixed $k \ge 5$.

preprint2020arXiv

$2$-Layer $k$-Planar Graphs: Density, Crossing Lemma, Relationships, and Pathwidth

The $2$-layer drawing model is a well-established paradigm to visualize bipartite graphs. Several beyond-planar graph classes have been studied under this model. Surprisingly, however, the fundamental class of $k$-planar graphs has been considered only for $k=1$ in this context. We provide several contributions that address this gap in the literature. First, we show tight density bounds for the classes of $2$-layer $k$-planar graphs with $k\in\{2,3,4,5\}$. Based on these results, we provide a Crossing Lemma for $2$-layer $k$-planar graphs, which then implies a general density bound for $2$-layer $k$-planar graphs. We prove this bound to be almost optimal with a corresponding lower bound construction. Finally, we study relationships between $k$-planarity and $h$-quasiplanarity in the $2$-layer model and show that $2$-layer $k$-planar graphs have pathwidth at most $k+1$.

preprint2020arXiv

On the Area Requirements of Planar Greedy Drawings of Triconnected Planar Graphs

In this paper we study the area requirements of planar greedy drawings of triconnected planar graphs. Cao, Strelzoff, and Sun exhibited a family $\cal H$ of subdivisions of triconnected plane graphs and claimed that every planar greedy drawing of the graphs in $\mathcal H$ respecting the prescribed plane embedding requires exponential area. However, we show that every $n$-vertex graph in $\cal H$ actually has a planar greedy drawing respecting the prescribed plane embedding on an $O(n)\times O(n)$ grid. This reopens the question whether triconnected planar graphs admit planar greedy drawings on a polynomial-size grid. Further, we provide evidence for a positive answer to the above question by proving that every $n$-vertex Halin graph admits a planar greedy drawing on an $O(n)\times O(n)$ grid. Both such results are obtained by actually constructing drawings that are convex and angle-monotone. Finally, we consider $α$-Schnyder drawings, which are angle-monotone and hence greedy if $α\leq 30^\circ$, and show that there exist planar triangulations for which every $α$-Schnyder drawing with a fixed $α<60^\circ$ requires exponential area for any resolution rule.

preprint2020arXiv

Planar L-Drawings of Bimodal Graphs

In a planar L-drawing of a directed graph (digraph) each edge e is represented as a polyline composed of a vertical segment starting at the tail of e and a horizontal segment ending at the head of e. Distinct edges may overlap, but not cross. Our main focus is on bimodal graphs, i.e., digraphs admitting a planar embedding in which the incoming and outgoing edges around each vertex are contiguous. We show that every plane bimodal graph without 2-cycles admits a planar L-drawing. This includes the class of upward-plane graphs. Finally, outerplanar digraphs admit a planar L-drawing - although they do not always have a bimodal embedding - but not necessarily with an outerplanar embedding.

preprint2019arXiv

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 crossed more than $k$ times. In this paper, we explore the relationship between $k$-planarity and $k$-quasiplanarity to show that, for $k \geq 2$, every $k$-planar simple topological graph can be transformed into a $(k+1)$-quasiplanar simple topological graph.

preprint2017arXiv

On Planar Greedy Drawings of 3-Connected Planar Graphs

A graph drawing is $\textit{greedy}$ if, for every ordered pair of vertices $(x,y)$, there is a path from $x$ to $y$ such that the Euclidean distance to $y$ decreases monotonically at every vertex of the path. Greedy drawings support a simple geometric routing scheme, in which any node that has to send a packet to a destination "greedily" forwards the packet to any neighbor that is closer to the destination than itself, according to the Euclidean distance in the drawing. In a greedy drawing such a neighbor always exists and hence this routing scheme is guaranteed to succeed. In 2004 Papadimitriou and Ratajczak stated two conjectures related to greedy drawings. The $\textit{greedy embedding conjecture}$ states that every $3$-connected planar graph admits a greedy drawing. The $\textit{convex greedy embedding conjecture}$ asserts that every $3$-connected planar graph admits a planar greedy drawing in which the faces are delimited by convex polygons. In 2008 the greedy embedding conjecture was settled in the positive by Leighton and Moitra. In this paper we prove that every $3$-connected planar graph admits a $\textit{planar}$ greedy drawing. Apart from being a strengthening of Leighton and Moitra's result, this theorem constitutes a natural intermediate step towards a proof of the convex greedy embedding conjecture.

preprint2016arXiv

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 surfaces different from the plane. Namely, we show that the problems of testing the existence of a level embedding of a level graph on the surface of the rolling cylinder or on the surface of the torus, respectively known by the name of $\textit{Cyclic Level Planarity}$ and $\textit{Torus Level Planarity}$, are polynomial-time solvable. Moreover, we show a complexity dichotomy for testing the $\textit{Simultaneous Level Planarity}$ of a set of level graphs, with respect to both the number of level graphs and the number of levels.

preprint2016arXiv

Computing NodeTrix Representations of Clustered Graphs

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 boundaries. We study the complexity of constructing NodeTrix representations focusing on planarity testing problems, and we show several NP-completeness results and some polynomial-time algorithms. Building on such algorithms we develop a JavaScript library for NodeTrix representations aimed at reducing the crossings between edges incident to the same matrix.

preprint2016arXiv

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 drawing with $p$ collinear vertices? This problem resides at the core of several graph drawing problems, including universal point subsets, untangling, and column planarity. The following results are known for it: Every $n$-vertex planar graph has a planar straight-line drawing with $Ω(\sqrt{n})$ collinear vertices; for every $n$, there is an $n$-vertex planar graph whose every planar straight-line drawing has $O(n^σ)$ collinear vertices, where $σ<0.986$; every $n$-vertex planar graph of treewidth at most two has a planar straight-line drawing with $Θ(n)$ collinear vertices. We extend the linear bound to planar graphs of treewidth at most three and to triconnected cubic planar graphs. This (partially) answers two open problems posed by Ravsky and Verbitsky [WG 2011:295--306]. Similar results are not possible for all bounded treewidth planar graphs or for all bounded degree planar graphs. For planar graphs of treewidth at most three, our results also imply asymptotically tight bounds for all of the other above mentioned graph drawing problems.

preprint2016arXiv

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 that there is a morph (i.e., a continuous transformation) between the two drawings that preserves straight-line planarity and consists of $O(n)$ steps, which we prove is optimal in the worst case. Each step is a unidirectional linear morph, which means that every vertex moves at constant speed along a straight line, and the lines are parallel although the vertex speeds may differ. Thus we provide an efficient version of Cairns' 1944 proof of the existence of straight-line planarity-preserving morphs for triangulated graphs, which required an exponential number of steps.

preprint2016arXiv

On the Complexity of Realizing Facial Cycles

We study the following combinatorial problem. Given a planar graph $G=(V,E)$ and a set of simple cycles $\mathcal C$ in $G$, find a planar embedding $\mathcal E$ of $G$ such that the number of cycles in $\mathcal C$ that bound a face in $\mathcal E$ is maximized. We establish a tight border of tractability for this problem in biconnected planar graphs by giving conditions under which the problem is NP-hard and showing that relaxing any of these conditions makes the problem polynomial-time solvable. Moreover, we give a $2$-approximation algorithm for series-parallel graphs and a $(4+\varepsilon)$-approximation for biconnected planar graphs.

preprint2016arXiv

Simultaneous Orthogonal Planarity

We introduce and study the $\textit{OrthoSEFE}-k$ problem: Given $k$ planar graphs each with maximum degree 4 and the same vertex set, do they admit an OrthoSEFE, that is, is there an assignment of the vertices to grid points and of the edges to paths on the grid such that the same edges in distinct graphs are assigned the same path and such that the assignment induces a planar orthogonal drawing of each of the $k$ graphs? We show that the problem is NP-complete for $k \geq 3$ even if the shared graph is a Hamiltonian cycle and has sunflower intersection and for $k \geq 2$ even if the shared graph consists of a cycle and of isolated vertices. Whereas the problem is polynomial-time solvable for $k=2$ when the union graph has maximum degree five and the shared graph is biconnected. Further, when the shared graph is biconnected and has sunflower intersection, we show that every positive instance has an OrthoSEFE with at most three bends per edge.

preprint2015arXiv

Intersection-Link Representations of Graphs

We consider drawings of graphs that contain dense subgraphs. We introduce intersection-link representations for such graphs, in which each vertex $u$ is represented by a geometric object $R(u)$ and in which each edge $(u,v)$ is represented by the intersection between $R(u)$ and $R(v)$ if it belongs to a dense subgraph or by a curve connecting the boundaries of $R(u)$ and $R(v)$ otherwise. We study a notion of planarity, called Clique Planarity, for intersection-link representations of graphs in which the dense subgraphs are cliques.

preprint2015arXiv

L-Drawings of Directed Graphs

We introduce L-drawings, a novel paradigm for representing directed graphs aiming at combining the readability features of orthogonal drawings with the expressive power of matrix representations. In an L-drawing, vertices have exclusive $x$- and $y$-coordinates and edges consist of two segments, one exiting the source vertically and one entering the destination horizontally. We study the problem of computing L-drawings using minimum ink. We prove its NP-completeness and provide a heuristics based on a polynomial-time algorithm that adds a vertex to a drawing using the minimum additional ink. We performed an experimental analysis of the heuristics which confirms its effectiveness.

preprint2015arXiv

Planarity of Streamed Graphs

In this paper we introduce a notion of planarity for graphs that are presented in a streaming fashion. A $\textit{streamed graph}$ is a stream of edges $e_1,e_2,...,e_m$ on a vertex set $V$. A streamed graph is $ω$-$\textit{stream planar}$ with respect to a positive integer window size $ω$ if there exists a sequence of planar topological drawings $Γ_i$ of the graphs $G_i=(V,\{e_j \mid i\leq j < i+ω\})$ such that the common graph $G^{i}_\cap=G_i\cap G_{i+1}$ is drawn the same in $Γ_i$ and in $Γ_{i+1}$, for $1\leq i < m-ω$. The $\textit{Stream Planarity}$ Problem with window size $ω$ asks whether a given streamed graph is $ω$-stream planar. We also consider a generalization, where there is an additional $\textit{backbone graph}$ whose edges have to be present during each time step. These problems are related to several well-studied planarity problems. We show that the $\textit{Stream Planarity}$ Problem is NP-complete even when the window size is a constant and that the variant with a backbone graph is NP-complete for all $ω\ge 2$. On the positive side, we provide $O(n+ωm)$-time algorithms for (i) the case $ω= 1$ and (ii) all values of $ω$ provided the backbone graph consists of one $2$-connected component plus isolated vertices and no stream edge connects two isolated vertices. Our results improve on the Hanani-Tutte-style $O((nm)^3)$-time algorithm proposed by Schaefer [GD'14] for $ω=1$.

preprint2014arXiv

Advancements on SEFE and Partitioned Book Embedding Problems

In this work we investigate the complexity of some problems related to the {\em Simultaneous Embedding with Fixed Edges} (SEFE) of $k$ planar graphs and the PARTITIONED $k$-PAGE BOOK EMBEDDING (PBE-$k$) problems, which are known to be equivalent under certain conditions. While the computational complexity of SEFE for $k=2$ is still a central open question in Graph Drawing, the problem is NP-complete for $k \geq 3$ [Gassner {\em et al.}, WG '06], even if the intersection graph is the same for each pair of graphs ({\em sunflower intersection}) [Schaefer, JGAA (2013)]. We improve on these results by proving that SEFE with $k \geq 3$ and sunflower intersection is NP-complete even when the intersection graph is a tree and all the input graphs are biconnected. Also, we prove NP-completeness for $k \geq 3$ of problem PBE-$k$ and of problem PARTITIONED T-COHERENT $k$-PAGE BOOK EMBEDDING (PTBE-$k$) - that is the generalization of PBE-$k$ in which the ordering of the vertices on the spine is constrained by a tree $T$ - even when two input graphs are biconnected. Further, we provide a linear-time algorithm for PTBE-$k$ when $k-1$ pages are assigned a connected graph. Finally, we prove that the problem of maximizing the number of edges that are drawn the same in a SEFE of two graphs is NP-complete in several restricted settings ({\em optimization version of SEFE}, Open Problem $9$, Chapter $11$ of the Handbook of Graph Drawing and Visualization).

preprint2014arXiv

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 straight-line drawing Γ of G in the plane such that the edges of S are not crossed in Γ by any edge of G? We give positive and negative results for different kinds of connected spanning subgraphs S of G. Moreover, in order to enlarge the subset of instances that admit a solution, we consider the possibility of bending the edges of G not in S; in this setting we discuss different trade-offs between the number of bends and the required drawing area.

preprint2014arXiv

Deepening the Relationship between SEFE and C-Planarity

In this paper we deepen the understanding of the connection between two long-standing Graph Drawing open problems, that is, Simultaneous Embedding with Fixed Edges (SEFE) and Clustered Planarity (C-PLANARITY). In his GD'12 paper Marcus Schaefer presented a reduction from C-PLANARITY to SEFE of two planar graphs (SEFE-2). We prove that a reduction exists also in the opposite direction, if we consider instances of SEFE-2 in which the intersection graph is connected. We pose as an open question whether the two problems are polynomial-time equivalent.

preprint2014arXiv

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 $O(n)$ morphing steps, thus improving upon the previously best known $O(n^2)$ upper bound. Further, we prove that our algorithm is optimal, that is, we show that there exist two planar straight-line drawings $Γ_s$ and $Γ_t$ of an $n$-vertex plane graph $G$ such that any planar morph between $Γ_s$ and $Γ_t$ requires $Ω(n)$ morphing steps.

preprint2014arXiv

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 UNIFORMFACES of embedding a given biconnected multi-graph such that the largest face is as small as possible and such that all faces have the same size, respectively. We prove a complexity dichotomy for MINMAXFACE and show that deciding whether the maximum is at most $k$ is polynomial-time solvable for $k \leq 4$ and NP-complete for $k \geq 5$. Further, we give a 6-approximation for minimizing the maximum face in a planar embedding. For UNIFORMFACES, we show that the problem is NP-complete for odd $k \geq 7$ and even $k \geq 10$. Moreover, we characterize the biconnected planar multi-graphs admitting 3- and 4-uniform embeddings (in a $k$-uniform embedding all faces have size $k$) and give an efficient algorithm for testing the existence of a 6-uniform embedding.

preprint2014arXiv

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 simple closed regions. A drawing of a clustered graph is c-planar if it has no edge-edge, edge-region, or region-region crossings. Determining the complexity of testing whether a clustered graph admits a c-planar drawing is a long-standing open problem in the Graph Drawing research area. An obvious necessary condition for c-planarity is the planarity of the graph underlying the clustered graph. However, such a condition is not sufficient and the consequences on the problem due to the requirement of not having edge-region and region-region crossings are not yet fully understood. In order to shed light on the c-planarity problem, we consider a relaxed version of it, where some kinds of crossings (either edge-edge, edge-region, or region-region) are allowed even if the underlying graph is planar. We investigate the relationships among the minimum number of edge-edge, edge-region, and region-region crossings for drawings of the same clustered graph. Also, we consider drawings in which only crossings of one kind are admitted. In this setting, we prove that drawings with only edge-edge or with only edge-region crossings always exist, while drawings with only region-region crossings may not. Further, we provide upper and lower bounds for the number of such crossings. Finally, we give a polynomial-time algorithm to test whether a drawing with only region-region crossings exist for biconnected graphs, hence identifying a first non-trivial necessary condition for c-planarity that can be tested in polynomial time for a noticeable class of graphs.

preprint2013arXiv

Strip Planarity Testing of 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 function $γ:V \rightarrow \{1,2,\dots,k\}$ and asks whether a planar drawing of $G$ exists such that each edge is monotone in the $y$-direction and, for any $u,v\in V$ with $γ(u)<γ(v)$, it holds $y(u)<y(v)$. The problem has strong relationships with some of the most deeply studied variants of the planarity testing problem, such as clustered planarity, upward planarity, and level planarity. We show that the problem is polynomial-time solvable if $G$ has a fixed planar embedding.