From the 1 of 9 linked papers with an AI index.
9 papers
Extending Biconnected Straight-Line Planar Drawings
Giordano Andreola, Susanna Caroppo, Giordano Da Lozzo +5
The paper investigates the difficulty of extending a straight-line planar drawing of a biconnected subgraph to the whole graph, showing NP‑hardness in the variable‑embedding case a…
Beyond Degree Four: Near-Orthogonal Planar Drawings
Patrizio Angelini, Sabine Cornelsen, Giordano Da Lozzo +2
Orthogonal planar drawings constitute a classical and mainstream research topic in graph drawing due to their clarity and wide applicability. In an orthogonal planar drawing of a g…
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…
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…
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…