5 citations · 14 across the 11 of their papers we have counts for
18 papers
Linear Layouts of Bipartite Planar Graphs
Henry Förster, Michael Kaufmann, Laura Merker +2
A linear layout of a graph consists of a linear order of the vertices and a partition of the edges. A part is called a queue (stack) if no two edges nest (cross), tha…
Testing Upward Planarity of Partial -Trees
Steven Chaplick, Emilio Di Giacomo, Fabrizio Frati +3
We present an -time algorithm to test whether an -vertex directed partial -tree is upward planar. This result improves upon the previously best known algorithm, which…
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…
Recognizing and Embedding Simple Optimal 2-Planar Graphs
Henry Förster, Michael Kaufmann, Chrysanthi N. Raftopoulou
In the area of beyond-planar graphs, i.e. graphs that can be drawn with some local restrictions on the edge crossings, the recognition problem is prominent next to the density ques…
On the Queue Number of Planar Graphs
Michael A. Bekos, Martin Gronemann, Chrysanthi N. Raftopoulou
A k-queue layout is a special type of a linear layout, in which the linear order avoids (k+1)-rainbows, i.e., k+1 independent edges that pairwise form a nested pair. The optimizati…
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…
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…
Coloring outerplanar graphs and planar 3-trees with small monochromatic components
Michael A. Bekos, Carla Binucci, Michael Kaufmann +3
In this work, we continue the study of vertex colorings of graphs, in which adjacent vertices are allowed to be of the same color as long as each monochromatic connected component…
On a Conjecture of Lovász on Circle-Representations of Simple 4-Regular Planar Graphs
Michael A. Bekos, Chrysanthi N. Raftopoulou
Lovász conjectured that every connected 4-regular planar graph G admits a realization as a system of circles, i.e., it can be drawn on the plane utilizing a set of circles, such th…
Planar Graphs of Bounded Degree have Constant Queue Number
Michael A. Bekos, Henry Förster, Martin Gronemann +4
A \emph{queue layout} of a graph consists of a \emph{linear order} of its vertices and a partition of its edges into \emph{queues}, so that no two independent edges of the same que…
Orthogonal and Smooth Orthogonal Layouts of 1-Planar Graphs with Low Edge Complexity
Evmorfia Argyriou, Sabine Cornelsen, Henry Förster +5
While orthogonal drawings have a long history, smooth orthogonal drawings have been introduced only recently. So far, only planar drawings or drawings with an arbitrary number of c…
Edge Partitions of Optimal -plane and -plane Graphs
Michael Bekos, Emilio Di Giacomo, Walter Didimo +3
A topological graph is a graph drawn in the plane. A topological graph is -plane, , if each edge is crossed at most times. We study the problem of partitioning the edge…
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 …
The Book Thickness of 1-Planar Graphs is Constant
Michael A. Bekos, Till Bruckdorfer, Michael Kaufmann +1
In a book embedding, the vertices of a graph are placed on the spine of a book and the edges are assigned to pages, so that edges on the same page do not cross. In this paper, we p…
Two-Page Book Embeddings of 4-Planar Graphs
Michael A. Bekos, Martin Gronemann, Chrysanthi N. Raftopoulou
Back in the Eighties, Heath showed that every 3-planar graph is subhamiltonian and asked whether this result can be extended to a class of graphs of degree greater than three. In t…