72 citations · 219 across the 12 of their papers we have counts for
Showing 2003Show all
3 papers · 1 filter
cs.CG2003★ 2 cited
The Geometric Thickness of Low Degree Graphs
Christian A. Duncan, David Eppstein, Stephen G. Kobourov
We prove that the geometric thickness of graphs whose maximum degree is no more than four is two. All of our algorithms run in O(n) time, where n is the number of vertices in the g…
cs.DS2003★ 2 cited
Quasiconvex Analysis of Backtracking Algorithms
David Eppstein
We consider a class of multivariate recurrences frequently arising in the worst case analysis of Davis-Putnam-style exponential time backtracking algorithms for NP-hard problems. W…
cs.CG2003★ 72 cited
Tiling space and slabs with acute tetrahedra
David Eppstein, John M. Sullivan, Alper Ungor
We show it is possible to tile three-dimensional space using only tetrahedra with acute dihedral angles. We present several constructions to achieve this, including one in which al…