6 papers
Signotopes Induce Unique Sink Orientations on Grids
Sandro M. Roch
A unique sink orientation (USO) is an orientation of the edges of a polytope in which every face contains a unique sink. For a product of simplices , Felsne…
Block coupling and rapidly mixing k-heights
Stefan Felsner, Daniel Heldt, Sandro Roch +1
A -height on a graph is an assignment such that the value on ajacent vertices differs by at most . We study the Markov chain on -heights…
Coloring problems on arrangements of pseudolines
Sandro Roch
Arrangements of pseudolines are a widely studied generalization of line arrangements. They are defined as a finite family of infinite curves in the Euclidean plane, any two of whic…
On exact covering with unit disks
Ji Hoon Chun, Christian Kipp, Sandro Roch
We study the problem of covering a given point set in the plane by unit disks so that each point is covered exactly once. We prove that 17 points can always be exactly covered. On…
Flip Graph Connectivity for Arrangements of Pseudolines and Pseudocircles
Yan Alves Radtke, Stefan Felsner, Johannes Obenaus +3
Flip graphs of combinatorial and geometric objects are at the heart of many deep structural insights and connections between different branches of discrete mathematics and computer…
Arrangements of Pseudocircles: On Digons and Triangles
Stefan Felsner, Sandro Roch, Manfred Scheucher
In this article, we study the cell-structure of simple arrangements of pairwise intersecting pseudocircles. The focus will be on two problems of Grünbaum (1972). First, we discuss…