research
∙
03/12/2023
Reconstructing Graphs from Connected Triples
We introduce a new model of indeterminacy in graphs: instead of specifyi...
share
research
∙
06/26/2021
Planar and Toroidal Morphs Made Easier
We present simpler algorithms for two closely related morphing problems,...
research
∙
03/17/2021
Chasing Puppies: Mobile Beacon Routing on Closed Curves
We solve an open problem posed by Michael Biro at CCCG 2013 that was ins...
research
∙
07/15/2020
How to Morph Graphs on the Torus
We present the first algorithm to morph graphs on the torus. Given two i...
research
∙
03/31/2020
Fusible numbers and Peano Arithmetic
Inspired by a mathematical riddle involving fuses, we define the "fusibl...
research
∙
03/23/2020
A Toroidal Maxwell-Cremona-Delaunay Correspondence
We consider three classes of geodesic embeddings of graphs on Euclidean ...
research
∙
12/04/2019
A Framework for Robust Realistic Geometric Computations
We propose a new paradigm for robust geometric computations that complem...
research
∙
10/09/2019
Minimum Cuts in Surface Graphs
We describe algorithms to efficiently compute minimum (s,t)-cuts and glo...
research
∙
08/25/2019
Optimal Curve Straightening is ∃R-Complete
We prove that the following problem has the same computational complexit...
research
∙
12/04/2018
Topologically Trivial Closed Walks in Directed Surface Graphs
Let G be a directed graph with n vertices and m edges, embedded on a sur...
research
∙
04/03/2018
Holiest Minimum-Cost Paths and Flows in Surface Graphs
Let G be an edge-weighted directed graph with n vertices embedded on an ...
research
∙
07/15/2017
Lower Bounds for Planar Electrical Reduction
We improve our earlier lower bounds on the number of electrical transfor...
research
∙
07/02/2002
Optimally cutting a surface into a disk
We consider the problem of cutting a set of edges on a polyhedral manifo...
research
∙
10/21/1999
Finite-resolution hidden surface removal
We propose a hybrid image-space/object-space solution to the classical h...
research
∙
09/18/1998