5 citations · 14 across the 11 of their papers we have counts for
6 papers · 1 filter
Recognizing DAGs with Page-Number 2 is NP-complete
Michael A. Bekos, Giordano Da Lozzo, Fabrizio Frati +3
The page-number of a directed acyclic graph (a DAG, for short) is the minimum for which the DAG has a topological order and a -coloring of its edges such that no two edges o…
Parameterized Algorithms for Upward Planarity
Steven Chaplick, Emilio Di Giacomo, Fabrizio Frati +3
We obtain new parameterized algorithms for the classical problem of determining whether a directed acyclic graph admits an upward planar drawing. Our results include a new fixed-pa…
Book Embeddings of Nonplanar Graphs with Small Faces in Few Pages
Michael A. Bekos, Giordano Da Lozzo, Svenja Griesbach +3
An embedding of a graph in a book, called book embedding, consists of a linear ordering of its vertices along the spine of the book and an assignment of its edges to the pages of t…
On Layered Fan-Planar Graph Drawings
Therese Biedl, Steven Chaplick, Jiři Fiala +4
In this paper, we study fan-planar drawings that use layers and are proper, i.e., edges connect adjacent layers. We show that if the embedding of the graph is fixed, then testi…
On Optimal 2- and 3-Planar Graphs
Michael A. Bekos, Michael Kaufmann, Chrysanthi N. Raftopoulou
A graph is -planar if it can be drawn in the plane such that no edge is crossed more than times. While for , optimal -planar graphs, i.e., those with vertices an…
On the Density of non-Simple 3-Planar Graphs
Michael A. Bekos, Michael Kaufmann, Chrysanthi N. Raftopoulou
A \emph{-planar graph} is a graph that can be drawn in the plane such that every edge is crossed at most times. For , Pach and Tóth proved a bound of …