5 papers
Geometric Give and Take
Oswin Aichholzer, Katharina Klost, Kristin Knorr +2
We consider a special, geometric case of a balancing game introduced by Spencer in 1977. Consider any arrangement of lines in the plane, and assume that each cell…
How many times can two minimum spanning trees cross?
Todor Antić, Morteza Saghafian, Maria Saumell +3
Let be a generic set of points in the plane, and let be a coloring of in two colors. We are interested in the number of crossings between the minimum spanni…
Minimum spanning blob-trees
Katharina Klost, Marc van Kreveld, Daniel Perz +2
We investigate blob-trees, a new way of connecting a set of points, by a mixture of enclosing them by cycles (as in the convex hull) and connecting them by edges (as in a spanning…
Disjoint Compatibility via Graph Classes
Oswin Aichholzer, Julia Obmann, Pavel Paták +3
Two plane drawings of graphs on the same set of points are called disjoint compatible if their union is plane and they do not have an edge in common. Let be a convex point set…
Flip Graphs of Pseudo-Triangulations With Face Degree at Most 4
Maarten Löffler, Tamara Mchedlidze, David Orden +2
A pseudo-triangle is a simple polygon with exactly three convex vertices, and all other vertices (if any) are distributed on three concave chains. A pseudo-triangulation~$\mathcal{…