38 citations · 68 across the 29 of their papers we have counts for
40 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…
A Walk on the Wild Side: a Shape-First Methodology for Orthogonal Drawings
Giordano Andreola, Susanna Caroppo, Giuseppe Di Battista +3
Several algorithms for the construction of orthogonal drawings of graphs, including those based on the Topology-Shape-Metrics (TSM) paradigm, tend to prioritize the minimization of…
Ranking and Unranking of the Planar Embeddings of a Planar Graph
Giuseppe Di Battista, Fabrizio Grosso, Giulia Maragno +1
Let be the set of all the planar embeddings of a (not necessarily connected) -vertex graph . We present a bijection from to the natural number…
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…
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…
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…
st-Orientations with Few Transitive Edges
Carla Binucci, Walter Didimo, Maurizio Patrignani
The problem of orienting the edges of an undirected graph such that the resulting digraph is acyclic and has a single source s and a single sink t has a long tradition in graph the…
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…
Planar Straight-line Realizations of 2-Trees with Prescribed Edge Lengths
Carlos Alegría, Manuel Borrazzo, Giordano Da Lozzo +3
We study a classic problem introduced thirty years ago by Eades and Wormald. Let be a weighted planar graph, where is a length function.…
2-Level Quasi-Planarity or How Caterpillars Climb (SPQR-)Trees
Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista +2
Given a bipartite graph , the -Level Quasi-Planarity problem asks for the existence of a drawing of in the plane such that the vertices in and in …
A Tipping Point for the Planarity of Small and Medium Sized Graphs
Emanuele Balloni, Giuseppe Di Battista, Maurizio Patrignani
This paper presents an empirical study of the relationship between the density of small-medium sized random graphs and their planarity. It is well known that, when the number of ve…
On Turn-Regular Orthogonal Representations
Michael A. Bekos, Carla Binucci, Giuseppe Di Battista +5
An interesting class of orthogonal representations consists of the so-called turn-regular ones, i.e., those that do not contain any pair of reflex corners that "point to each other…
Schematic Representation of Large Biconnected Graphs
Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani +1
Suppose that a biconnected graph is given, consisting of a large component plus several other smaller components, each separated from the main component by a separation pair. We in…
Optimal Orthogonal Drawings of Planar 3-Graphs in Linear Time
Walter Didimo, Giuseppe Liotta, Giacomo Ortali +1
A planar orthogonal drawing of a planar graph is a geometric representation of such that the vertices are drawn as distinct points of the plane, the edges are drawn as…
How to Morph a Tree on a Small Grid
Fidel Barrera-Cruz, Manuel Borrazzo, Giordano Da Lozzo +4
In this paper we study planar morphs between straight-line planar grid drawings of trees. A morph consists of a sequence of morphing steps, where in a morphing step vertices move a…
Graph Stories in Small Area
Manuel Borrazzo, Giordano Da Lozzo, Giuseppe Di Battista +2
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 a fixed amount of time, called the window siz…
The QuaSEFE Problem
Patrizio Angelini, Henry Förster, Michael Hoffmann +4
We initiate the study of Simultaneous Graph Embedding with Fixed Edges in the beyond planarity framework. In the QuaSEFE problem, we allow edge crossings, as long as each graph ind…
Upward Book Embeddings of st-Graphs
Carla Binucci, Giordano Da Lozzo, Emilio Di Giacomo +3
We study -page upward book embeddings (UBEs) of -graphs, that is, book embeddings of single-source single-sink directed acyclic graphs on pages with the additional re…
On the Area Requirements of Planar Straight-Line Orthogonal Drawings of Ternary Trees
Barbara Covella, Fabrizio Frati, Maurizio Patrignani
In this paper, we study the area requirements of planar straight-line orthogonal drawings of ternary trees. We prove that every ternary tree admits such a drawing in sub-quadratic…
Clustered Planarity = Flat Clustered Planarity
Pier Francesco Cortese, Maurizio Patrignani
The complexity of deciding whether a clustered graph admits a clustered planar drawing is a long-standing open problem in the graph drawing research area. Several research efforts…
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…
Bend-minimum Orthogonal Drawings in Quadratic Time
Walter Didimo, Giuseppe Liotta, Maurizio Patrignani
Let be a planar -graph (i.e., a planar graph with vertex degree at most three) with vertices. We present the first -time algorithm that computes a planar orthogo…
Planar L-Drawings of Directed Graphs
Steven Chaplick, Markus Chimani, Sabine Cornelsen +5
We study planar drawings of directed graphs in the L-drawing standard. We provide necessary conditions for the existence of these drawings and show that testing for the existence o…