Publications (7)
Arc diagrams, flip distances, and Hamiltonian triangulations
Jean Cardinal, Michael Hoffmann, Vincent Kusters +2
We show that every triangulation (maximal planar graph) on vertices can be flipped into a Hamiltonian triangulation using a sequence of less than combinatorial edge…
Simultaneous Embeddings with Few Bends and Crossings
Fabrizio Frati, Michael Hoffmann, Vincent Kusters
A simultaneous embedding with fixed edges (SEFE) of two planar graphs and is a pair of plane drawings of and that coincide when restricted to the common vertices an…
On Universal Point Sets for Planar Graphs
Jean Cardinal, Michael Hoffmann, Vincent Kusters
A set P of points in R^2 is n-universal, if every planar graph on n vertices admits a plane straight-line embedding on P. Answering a question by Kobourov, we show that there is no…
The Planar Tree Packing Theorem
Markus Geyer, Michael Hoffmann, Michael Kaufmann +2
Packing graphs is a combinatorial problem where several given graphs are being mapped into a common host graph such that every edge is used at most once. In the planar tree packing…
The Complexity of Simultaneous Geometric Graph Embedding
Jean Cardinal, Vincent Kusters
Given a collection of planar graphs on the same set of vertices, the simultaneous geometric embedding (with mapping) problem, or simply -SGE, is to find…
Halving Balls in Deterministic Linear Time
Michael Hoffmann, Vincent Kusters, Tillmann Miltzow
Let $\D$ be a set of pairwise disjoint unit balls in and the set of their center points. A hyperplane $\Hy$ is an \emph{-separator} for $\D$ if each closed halfsp…
An Optimal Algorithm for Reconstructing Point Set Order Types from Radial Orderings
Oswin Aichholzer, Vincent Kusters, Wolfgang Mulzer +2
Let be a set of labeled points in the plane. The radial system of describes, for each , the order in which a ray that rotates around encounters the points i…