1 citations · 1 across the 9 of their papers we have counts for
13 papers
Simultaneous Embedding of Two Paths on the Grid
Stephen Kobourov, William Lenhart, Giuseppe Liotta +3
Simultaneous geometric embedding of graphs on an integer grid is a classical research topic in Graph Drawing. When the graphs are two paths, one can additionally require that one p…
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…
No Selection Lemma for Empty Triangles
Ruy Fabila-Monroy, Carlos Hidalgo-Toscano, Daniel Perz +1
Let be a set of points in general position in the plane. The Second Selection Lemma states that for any family of triangles spanned by , there exists a point of…
Nearest-Neighbor Decompositions of Drawings
Jonas Cleve, Nicolas Grelier, Kristin Knorr +3
Let be a set of straight-line segments in the plane, potentially crossing, and let be a positive integer. We denote by the union of the endpoints of the strai…
Finding a Battleship of Uncertain Shape
Eva-Maria Hainzl, Maarten Löffler, Daniel Perz +2
Motivated by a game of Battleship, we consider the problem of efficiently hitting a ship of an uncertain shape within a large playing board. Formally, we fix a dimension $d\in\{1,2…
On Compatible Matchings
Oswin Aichholzer, Alan Arroyo, Zuzana Masárová +5
A matching is compatible to two or more labeled point sets of size with labels if its straight-line drawing on each of these point sets is crossing-free. We stu…
Plane Spanning Trees in Edge-Colored Simple Drawings of
Oswin Aichholzer, Michael Hoffmann, Johannes Obenaus +5
Károlyi, Pach, and Tóth proved that every 2-edge-colored straight-line drawing of the complete graph contains a monochromatic plane spanning tree. It is open if this statement gene…
Empty Rainbow Triangles in -colored Point Sets
Ruy Fabila-Monroy, Daniel Perz, Ana Laura Trujillo-Negrete
Let be a set of points in general position in the plane. Suppose that each point of has been assigned one of possible colors and that there is the same number…
Graphs with large total angular resolution
Oswin Aichholzer, Matias Korman, Yoshio Okamoto +4
The total angular resolution of a straight-line drawing is the minimum angle between two edges of the drawing. It combines two properties contributing to the readability of a drawi…