5 papers
Ramsey Meets Simultaneous Planarity: Vertex Integrity and Pathwidth
Thomas Depian, Simon D. Fink, Alexander Firbas +3
We study the following simultaneous embedding problem: Given k graphs on the same vertex set with the same pairwise intersection, do they admit planar drawings that coincide on the…
Monotone Clustered Level Planarity
Simon D. Fink, Matthias Pfretzschner, Ignaz Rutter +1
We consider the combination of the two constrained planarity problems Level- and Clustered Planarity. Traditionally, level-planar drawings with convex clusters have been studied in…
Crossing Number of 3-Plane Drawings
Miriam Goetze, Michael Hoffmann, Ignaz Rutter +1
We study 3-plane drawings, that is, drawings of graphs in which every edge has at most three crossings. We show how the recently developed Density Formula for topological drawings…
A Simple Partially Embedded Planarity Test Based on Vertex-Addition
Simon D. Fink, Ignaz Rutter, Sandhya T. P
In the Partially Embedded Planarity problem, we are given a graph together with a topological drawing of a subgraph of . The task is to decide whether the drawing can be…
Level Planarity Is More Difficult Than We Thought
Simon D. Fink, Matthias Pfretzschner, Ignaz Rutter +1
We consider three simple quadratic time algorithms for the problem Level Planarity and give a level-planar instance that they either falsely report as negative or for which they ou…