12 citations · 39 across the 22 of their papers we have counts for
24 papers
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…
Upward Pointset Embeddings of Planar st-Graphs
Carlos Alegria, Susanna Caroppo, Giordano Da Lozzo +5
We study upward pointset embeddings (UPSEs) of planar -graphs. Let be a planar -graph and let be a pointset with . An UPSE of …
Efficient Enumeration of Drawings and Combinatorial Structures for Maximal Planar Graphs
Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati +2
We propose efficient algorithms for enumerating the notorious combinatorial structures of maximal planar graphs, called canonical orderings and Schnyder woods, and the related clas…
Min--planar Drawings of Graphs
Carla Binucci, Aaron Büngener, Giuseppe Di Battista +7
The study of nonplanar drawings of graphs with restricted crossing configurations is a well-established topic in graph drawing, often referred to as beyond-planar graph drawing. On…
Treebar Maps: Schematic Representation of Networks at Scale
Giuseppe Di Battista, Fabrizio Grosso, Silvia Montorselli +1
Many data sets, crucial for today's applications, consist essentially of enormous networks, containing millions or even billions of elements. Having the possibility of visualizing…
Quantum Graph Drawing
Susanna Caroppo, Giordano Da Lozzo, Giuseppe Di Battista
In this paper, we initiate the study of quantum algorithms in the Graph Drawing research area. We focus on two foundational drawing standards: 2-level drawings and book layouts. Co…
Splitting Vertices in 2-Layer Graph Drawings
Reyan Ahmed, Patrizio Angelini, Michael A. Bekos +8
Bipartite graphs model the relationships between two disjoint sets of entities in several applications and are naturally drawn as 2-layer graph drawings. In such drawings, the two…
Small Point-Sets Supporting Graph Stories
Giuseppe Di Battista, Walter Didimo, Luca Grilli +4
In a graph story the vertices enter a graph one at a time and each vertex persists in the graph for a fixed amount of time , called viewing window. At any time, the user can see…
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…
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…
Upward Planar Morphs
Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati +2
We prove that, given two topologically-equivalent upward planar straight-line drawings of an -vertex directed graph , there always exists a morph between them such that all t…
On the Relationship between -Planar and -Quasi Planar Graphs
Patrizio Angelini, Michael A. Bekos, Franz J. Brandenburg +6
A graph is -planar if it can be drawn in the plane such that no edge is crossed more than times. A graph is -quasi planar if it can be drawn 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…
Simultaneous Orthogonal Planarity
Patrizio Angelini, Steven Chaplick, Sabine Cornelsen +7
We introduce and study the problem: Given planar graphs each with maximum degree 4 and the same vertex set, do they admit an OrthoSEFE, that is, is there…
Beyond Level Planarity
Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista +3
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…
Windrose Planarity: Embedding Graphs with Direction-Constrained Edges
Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista +4
Given a planar graph and a partition of the neighbors of each vertex in four sets , , , and , the problem Windrose Planarity asks to decide whet…
Intersection-Link Representations of Graphs
Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista +3
We consider drawings of graphs that contain dense subgraphs. We introduce intersection-link representations for such graphs, in which each vertex is represented by a geometric…
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.
Advances on Testing C-Planarity of Embedded Flat Clustered Graphs
Markus Chimani, Giuseppe Di Battista, Fabrizio Frati +1
We show a polynomial-time algorithm for testing c-planarity of embedded flat clustered graphs with at most two vertices per cluster on each face.
On the Complexity of Clustered-Level Planarity and T-Level Planarity
Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista +2
In this paper we study two problems related to the drawing of level graphs, that is, T-LEVEL PLANARITY and CLUSTERED-LEVEL PLANARITY. We show that both problems are NP-complete in…
Morphing Planar Graph Drawings Optimally
Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista +3
We provide an algorithm for computing a planar morph between any two planar straight-line drawings of any -vertex plane graph in morphing steps, thus improving upon the p…
From BGP to RTT and Beyond: Matching BGP Routing Changes and Network Delay Variations with an Eye on Traceroute Paths
Massimo Rimondini, Claudio Squarcella, Giuseppe Di Battista
Many organizations have the mission of assessing the quality of broadband access services offered by Internet Service Providers (ISPs). They deploy network probes that periodically…
Relaxing the Constraints of Clustered Planarity
Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista +3
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…
Computational Complexity of Traffic Hijacking under BGP and S-BGP
Marco Chiesa, Giuseppe Di Battista, Thomas Erlebach +1
Harmful Internet hijacking incidents put in evidence how fragile the Border Gateway Protocol (BGP) is, which is used to exchange routing information between Autonomous Systems (ASe…