6 papers · 1 filter
Simultaneous Embedding of Two Paths on the Grid
Stephen Kobourov, William Lenhart, Giuseppe Liotta +3
We study the problem of simultaneous geometric embedding of two paths without self-intersections on an integer grid. We show that minimizing the length of the longest edge of such…
Flipping odd matchings in geometric and combinatorial settings
Oswin Aichholzer, Sofia Brenner, Joseph Dorfer +4
We study the problem of reconfiguring odd matchings, that is, matchings that cover all but a single vertex. Our reconfiguration operation is a so-called flip where the unmatched ve…
Flipping Matchings is Hard
Carla Binucci, Fabrizio Montecchiani, Daniel Perz +1
Given a point set and a plane perfect matching on , a flip is an operation that replaces two edges of such that another plane…
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…
Flips in Odd Matchings
Oswin Aichholzer, Anna Brötzner, Daniel Perz +1
Let be a set of points in the plane in general position. We define the graph whose vertex set is the set of all plane matchings on $\mathcal…
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…