21 citations · 92 across the 45 of their papers we have counts for
4 papers · 1 filter
The Maximum k-Differential Coloring Problem
Michael Bekos, Stephen Kobourov, Michael Kaufmann +1
Given an -vertex graph and two positive integers , the ()-differential coloring problem asks for a coloring of the vertices of (if one exists)…
On the Recognition of Fan-Planar and Maximal Outer-Fan-Planar Graphs
Michael A. Bekos, Sabine Cornelsen, Luca Grilli +2
Fan-planar graphs were recently introduced as a generalization of 1-planar graphs. A graph is fan-planar if it can be embedded in the plane, such that each edge that is crossed mor…
Improved Approximation Algorithms for Box Contact Representations
Michael A. Bekos, Thomas C. van Dijk, Martin Fink +5
We study the following geometric representation problem: Given a graph whose vertices correspond to axis-aligned rectangles with fixed dimensions, arrange the rectangles without ov…
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…