18 papers
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…