56 citations · 204 across the 25 of their papers we have counts for
28 papers
Reconstructing Graphs from Connected Triples
Paul Bastide, Linda Cook, Jeff Erickson +4
We introduce a new model of indeterminacy in graphs: instead of specifying all the edges of the graph, the input contains all triples of vertices that form a connected subgraph. In…
Planar and Toroidal Morphs Made Easier
Jeff Erickson, Patrick Lin
We present simpler algorithms for two closely related morphing problems, both based on the barycentric interpolation paradigm introduced by Floater and Gotsman, which is in turn ba…
Chasing Puppies: Mobile Beacon Routing on Closed Curves
Mikkel Abrahamsen, Jeff Erickson, Irina Kostitsyna +5
We solve an open problem posed by Michael Biro at CCCG 2013 that was inspired by his and others' work on beacon-based routing. Consider a human and a puppy on a simple closed curve…
Optimal Curve Straightening is -Complete
Jeff Erickson
We prove that the following problem has the same computational complexity as the existential theory of the reals: Given a generic self-intersecting closed curve in the plane an…
Topologically Trivial Closed Walks in Directed Surface Graphs
Jeff Erickson, Yipu Wang
Let be a directed graph with vertices and edges, embedded on a surface , possibly with boundary, with first Betti number . We consider the complexity of finding c…
Holiest Minimum-Cost Paths and Flows in Surface Graphs
Jeff Erickson, Kyle Fox, Luvsandondov Lkhamsuren
Let be an edge-weighted directed graph with vertices embedded on an orientable surface of genus . We describe a simple deterministic lexicographic perturbation scheme th…