12 citations · 13 across the 8 of their papers we have counts for
8 papers
Upward Book Embeddings of Partitioned Digraphs
Giordano Da Lozzo, Fabrizio Frati, Ignaz Rutter
In 1999, Heath, Pemmaraju, and Trenk [SIAM J. Comput. 28(4), 1999] extended the classic notion of book embeddings to digraphs, introducing the concept of upward book embeddings, in…
Quantum Speedups for Polynomial-Time Dynamic Programming Algorithms
Susanna Caroppo, Giordano Da Lozzo, Giuseppe Di Battista +2
We introduce a quantum dynamic programming framework that allows us to directly extend to the quantum realm a large body of classical dynamic programming algorithms. The correspond…
Grandchildren-weight-balanced binary search trees
Vincent Jugé
We revisit weight-balanced trees, also known as trees of bounded balance. This class of binary search trees was invented by Nievergelt and Reingold in 1972. Such trees are obtained…
The Price of Upwardness
Patrizio Angelini, Therese Biedl, Markus Chimani +8
Not every directed acyclic graph (DAG) whose underlying undirected graph is planar admits an upward planar drawing. We are interested in pushing the notion of upward drawings beyon…
On the Upward Book Thickness Problem: Combinatorial and Complexity Results
Sujoy Bhore, Giordano Da Lozzo, Fabrizio Montecchiani +1
A long-standing conjecture by Heath, Pemmaraju, and Trenk states that the upward book thickness of outerplanar DAGs is bounded above by a constant. In this paper, we show that the…
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 …
Simple -Planar Graphs are Simple -Quasiplanar
Patrizio Angelini, Michael A. Bekos, Franz J. Brandenburg +8
A simple topological graph is -quasiplanar () if it contains no pairwise crossing edges, and -planar if no edge is crossed more than times. In this paper, we…
Strip Planarity Testing of Embedded Planar Graphs
Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista +1
In this paper we introduce and study the strip planarity testing problem, which takes as an input a planar graph and a function and asks…