6 papers
Upward-Planar Drawings with Bounded Span
Patrizio Angelini, Sabine Cornelsen, Giordano Da Lozzo +4
We consider upward-planar layered drawings of directed graphs, i.e., crossing-free drawings in which each edge is drawn as a y-monotone curve going upward from its tail to its head…
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…
Large Induced Subgraphs of Bounded Degree in Outerplanar and Planar Graphs
Marco D'Elia, Fabrizio Frati
In this paper, we study the following question. Let be a family of planar graphs and let be an integer. What is the largest value such that every $n…
Internally-Convex Drawings of Outerplanar Graphs in Small Area
Michael A. Bekos, Giordano Da Lozzo, Fabrizio Frati +2
A well-known result by Kant [Algorithmica, 1996] implies that -vertex outerplane graphs admit embedding-preserving planar straight-line grid drawings where the internal faces ar…
Finding a Shortest Curve that Separates Few Objects from Many
Therese Biedl, Ãric Colin de Verdière, Fabrizio Frati +2
We present a fixed-parameter tractable (FPT) algorithm to find a shortest curve that encloses a set of k required objects in the plane while paying a penalty for enclosing unwanted…
Weakly Leveled Planarity with Bounded Span
Michael Bekos, Giordano Da Lozzo, Fabrizio Frati +5
This paper studies planar drawings of graphs in which each vertex is represented as a point along a sequence of horizontal lines, called levels, and each edge is either a horizonta…