9 citations · 16 across the 13 of their papers we have counts for
19 papers
Splitting Plane Graphs to Outerplanarity
Martin Gronemann, Martin Nöllenburg, Anaïs Villedieu
Vertex splitting replaces a vertex by two copies and partitions its incident edges amongst the copies. This problem has been studied as a graph editing operation to achieve desired…
Strictly-Convex Drawings of -Connected Planar Graphs
Michael A. Bekos, Martin Gronemann, Fabrizio Montecchiani +1
Strictly-convex straight-line drawings of -connected planar graphs in small area form a classical research topic in Graph Drawing. Currently, the best-known area bound for such…
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…
Recognizing Map Graphs of Bounded Treewidth
Patrizio Angelini, Michael A. Bekos, Giordano Da Lozzo +3
A map graph is a graph admitting a representation in which vertices are nations on a spherical map and edges are shared curve segments or points between nations. We present an expl…
Convex Grid Drawings of Planar Graphs with Constant Edge-Vertex Resolution
Michael A. Bekos, Martin Gronemann, Fabrizio Montecchiani +1
We continue the study of the area requirement of convex straight-line grid drawings of 3-connected plane graphs, which has been intensively investigated in the last decades. Motiva…
The Mixed Page Number of Graphs
Jawaherul Md. Alam, Michael A. Bekos, Martin Gronemann +2
A linear layout of a graph typically consists of a total vertex order, and a partition of the edges into sets of either non-crossing edges, called stacks, or non-nested edges, call…
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…
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…
On Turn-Regular Orthogonal Representations
Michael A. Bekos, Carla Binucci, Giuseppe Di Battista +5
An interesting class of orthogonal representations consists of the so-called turn-regular ones, i.e., those that do not contain any pair of reflex corners that "point to each other…
Drawing Shortest Paths in Geodetic Graphs
Sabine Cornelsen, Maximilian Pfister, Henry Förster +4
Motivated by the fact that in a space where shortest paths are unique, no two shortest paths meet twice, we study a question posed by Greg Bodwin: Given a geodetic graph , i.e.,…
Grid Drawings of Graphs with Constant Edge-Vertex Resolution
Michael A. Bekos, Martin Gronemann, Fabrizio Montecchiani +3
We study the algorithmic problem of computing drawings of graphs in which each vertex is a disk with fixed radius , each edge is a straight-line segment connecting…
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…
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…
Queue Layouts of Planar 3-Trees
Jawaherul Md. Alam, Michael A. Bekos, Martin Gronemann +2
A queue layout of a graph G consists of a linear order of the vertices of G and a partition of the edges of G into queues, so that no two independent edges of the same queue are ne…
Multi-Level Steiner Trees
Reyan Ahmed, Patrizio Angelini, Faryad Darabi Sahneh +8
In the classical Steiner tree problem, given an undirected, connected graph with non-negative edge costs and a set of \emph{terminals} , the objective is to…
On Dispersable Book Embeddings
Jawaherul Md. Alam, Michael A. Bekos, Martin Gronemann +2
In a dispersable book embedding, the vertices of a given graph must be ordered along a line l, called spine, and the edges of G must be drawn at different half-planes bounded b…
Bitonic st-orderings for Upward Planar Graphs
Martin Gronemann
Canonical orderings serve as the basis for many incremental planar drawing algorithms. All these techniques, however, have in common that they are limited to undirected graphs. Whi…
Crossing Minimization in Storyline Visualization
Martin Gronemann, Michael Jünger, Frauke Liers +1
A storyline visualization is a layout that represents the temporal dynamics of social interactions along time by the convergence of chronological lines. Among the criteria oriented…
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…