9 citations · 13 across the 3 of their papers we have counts for
10 papers
Distance-2 Edge Coloring is NP-Complete
Jeff Erickson, Shripad Thite, David P. Bunde
We prove that it is NP-complete to determine whether there exists a distance-2 edge coloring (strong edge coloring) with 5 colors of a bipartite 2-inductive graph with girth 6 and…
Optimally cutting a surface into a disk
Jeff Erickson, Sariel Har-Peled
We consider the problem of cutting a set of edges on a polyhedral manifold surface, possibly with boundary, to obtain a single topological disk, minimizing either the total number…
Building Space-Time Meshes over Arbitrary Spatial Domains
Jeff Erickson, Damrong Guoy, John M. Sullivan +1
We present an algorithm to construct meshes suitable for space-time discontinuous Galerkin finite-element methods. Our method generalizes and improves the `Tent Pitcher' algorithm…
Preprocessing Chains for Fast Dihedral Rotations Is Hard or Even Impossible
Michael Soss, Jeff Erickson, Mark Overmars
We examine a computational geometric problem concerning the structure of polymers. We model a polymer as a polygonal chain in three dimensions. Each edge splits the polymer into tw…
Vertex-Unfoldings of Simplicial Manifolds
Erik D. Demaine, David Eppstein, Jeff Erickson +2
We present an algorithm to unfold any triangulated 2-manifold (in particular, any simplicial polyhedron) into a non-overlapping, connected planar layout in linear time. The manifol…
Dense point sets have sparse Delaunay triangulations
Jeff Erickson
The spread of a finite set of points is the ratio between the longest and shortest pairwise distances. We prove that the Delaunay triangulation of any set of n points in R^3 with s…