1 citations · 3 across the 14 of their papers we have counts for
16 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…
The (Parameterized) Complexity of Ordering a Graph While Avoiding a Forbidden Pattern
Thomas Depian, Simon D. Fink, Alexander Firbas +3
In this paper, we study the Pattern Avoidance problem of determining whether a given graph admits a linear vertex order which avoids a given pattern , i.e., a vertex sequenc…
On Reconstructing a Convex Polygon from Partial Information
Alexander Baumann, Therese Biedl, Mahmoud Elashmawi +3
The reconstruction problem asks to construct a (convex) polygon that has a specified set of features, such as an ordered set of edge-lengths or an ordered set of polygon-angles. In…
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…
Garment numbers of bi-colored point sets in the plane
Oswin Aichholzer, Helena Bergold, Simon D. Fink +3
We consider colored variants of a class of geometric-combinatorial questions on -gons and empty -gons that have been started around 1935 by Erdős and Szekeres. In our setting…
Hexasort -- The Complexity of Stacking Colors on Graphs
Linus Klocker, Simon D. Fink
Many popular puzzle and matching games have been analyzed through the lens of computational complexity. Prominent examples include Sudoku, Candy Crush, and Flood-It. A common theme…
Linear Layouts Revisited: Stacks, Queues, and Exact Algorithms
Thomas Depian, Simon D. Fink, Robert Ganian +1
In spite of the extensive study of stack and queue layouts, many fundamental questions remain open concerning the complexity-theoretic frontiers for computing stack and queue layou…
The Peculiarities of Extending Queue Layouts
Thomas Depian, Simon D. Fink, Robert Ganian +1
We consider the problem of computing -page queue layouts, which are linear arrangements of vertices accompanied with an assignment of the edges to pages from one to th…
Pathways to Tractability for Geometric Thickness
Thomas Depian, Simon Dominik Fink, Alexander Firbas +2
We study the classical problem of computing geometric thickness, i.e., finding a straight-line drawing of an input graph and a partition of its edges into as few parts as possible…
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…
The Parameterized Complexity of Extending Stack Layouts
Thomas Depian, Simon D. Fink, Robert Ganian +1
An -page stack layout (also known as an -page book embedding) of a graph is a linear order of the vertex set together with a partition of the edge set into stack…
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…
Constrained Planarity in Practice -- Engineering the Synchronized Planarity Algorithm
Simon D. Fink, Ignaz Rutter
In the constrained planarity setting, we ask whether a graph admits a planar drawing that additionally satisfies a given set of constraints. These constraints are often derived fro…
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…
Maintaining Triconnected Components under Node Expansion
Simon D. Fink, Ignaz Rutter
SPQR-trees are a central component of graph drawing and are also important in many further areas of computer science. From their inception onwards, they have always had a strong re…