8 papers
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…
On Reconstructing a Convex Polygon from Partial Information
Alexander Baumann, Therese Biedl, Mahmoud Elashmawi +4
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…
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 settin…
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…