7 papers
Polygon-Universal Graphs
Tim Ophelders, Ignaz Rutter, Bettina Speckmann +1
We study a fundamental question from graph drawing: given a pair of a graph and a cycle in together with a simple polygon , is there a straight-line drawing…
Automatic Tree Ring Detection using Jacobi Sets
Kayla Makela, Tim Ophelders, Michelle Quigley +3
Tree ring widths are an important source of climatic and historical data, but measuring these widths typically requires extensive manual work. Computer vision techniques provide pr…
Between Shapes, Using the Hausdorff Distance
Marc van Kreveld, Tillmann Miltzow, Tim Ophelders +2
Given two shapes and in the plane with Hausdorff distance , is there a shape with Hausdorff distance to and from and ? The answer is always yes, and dep…
Homotopy height, grid-major height and graph-drawing height
Therese Biedl, Erin Wolf Chambers, David Eppstein +2
It is well-known that both the pathwidth and the outer-planarity of a graph can be used to obtain lower bounds on the height of a planar straight-line drawing of a graph. But both…
SETH Says: Weak Fréchet Distance is Faster, but only if it is Continuous and in One Dimension
Kevin Buchin, Tim Ophelders, Bettina Speckmann
We show by reduction from the Orthogonal Vectors problem that algorithms with strongly subquadratic running time cannot approximate the Fréchet distance between curves better than…
On the complexity of optimal homotopies
Erin Wolf Chambers, Arnaud de Mesmay, Tim Ophelders
In this article, we provide new structural results and algorithms for the Homotopy Height problem. In broad terms, this problem quantifies how much a curve on a surface needs to be…