1 citations · 2 across the 8 of their papers we have counts for
11 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…
Point Set Embeddability with List Constraints
Thomas Depian, Joseph Dorfer, Boris Klemz +2
Deciding whether a given graph admits a planar straight-line drawing where each vertex is placed on some point from a given finite point set is known as Point Set Embeddability and…
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…
Saturated Drawings of Geometric Thickness k
Patricia Bachmann, Anna Brötzner, Miriam Goetze +3
We investigate saturated geometric drawings of graphs with geometric thickness , where no edge can be added without increasing . We establish lower and upper bounds on the nu…
Segment Intersection Representations, Level Planarity and Constrained Ordering Problems
Simon D. Fink, Matthias Pfretzschner, Peter Stumpf
In the Segment Intersection Graph Representation Problem, we want to represent the vertices of a graph as straight line segments in the plane such that two segments cross if and on…
Unbent Collections of Orthogonal Drawings
Todor Antić, Giuseppe Liotta, Tomáš Masařík +5
Recently, there has been interest in representing single graphs by multiple drawings; for example, using graph stories, storyplans, or uncrossed collections. In this paper, we appl…
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…
Clustered Planarity Variants for Level Graphs
Simon D. Fink, Matthias Pfretzschner, Ignaz Rutter +1
We consider variants of the clustered planarity problem for level-planar drawings. So far, only convex clusters have been studied in this setting. We introduce two new variants tha…
Parameterized Complexity of Simultaneous Planarity
Simon D. Fink, Matthias Pfretzschner, Ignaz Rutter
Given input graphs , where each pair , with shares the same graph , the problem Simultaneous Embedding With Fixed Edges (SEFE) asks wh…
Parameterized Complexity of Vertex Splitting to Pathwidth at most 1
Jakob Baumann, Matthias Pfretzschner, Ignaz Rutter
Motivated by the planarization of 2-layered straight-line drawings, we consider the problem of modifying a graph such that the resulting graph has pathwidth at most 1. The problem…
Experimental Comparison of PC-Trees and PQ-Trees
Simon D. Fink, Matthias Pfretzschner, Ignaz Rutter
PQ-trees and PC-trees are data structures that represent sets of linear and circular orders, respectively, subject to constraints that specific subsets of elements have to be conse…