84 citations · 92 across the 11 of their papers we have counts for
5 papers · 1 filter
Lazy Queue Layouts of Posets
Jawaherul Md. Alam, Michael A. Bekos, Martin Gronemann +2
We investigate the queue number of posets in terms of their width, that is, the maximum number of pairwise incomparable elements. A long-standing conjecture of Heath and Pemmaraju…
Rectilinear Planarity Testing of Plane Series-Parallel Graphs in Linear Time
Walter Didimo, Michael Kaufmann, Giuseppe Liotta +1
A plane graph is rectilinear planar if it admits an embedding-preserving straight-line drawing where each edge is either horizontal or vertical. We prove that rectilinear planarity…
Four Pages Are Indeed Necessary for Planar Graphs
Michael A. Bekos, Michael Kaufmann, Fabian Klute +3
An embedding of a graph in a book consists of a linear order of its vertices along the spine of the book and of an assignment of its edges to the pages of the book, so that no two…
Monotone Arc Diagrams with few Biarcs
Steven Chaplick, Henry Förster, Michael Hoffmann +1
We show that every planar graph can be represented by a monotone topological 2-page book embedding where at most 15n/16 (of potentially 3n-6) edges cross the spine exactly once.
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…