# David Eppstein - Publications

##
Publications with Rasmus Tamstorf

**Approximate Topological Matching of Quadrilateral Meshes**.

D. Eppstein,
M. T. Goodrich,
E. Kim,
and R. Tamstorf.

*Proc. IEEE
Int. Conf. Shape Modeling and Applications (SMI 2008)*, Stony Brook,
New York, pp. 83–92.

*The Visual Computer*
25 (8): 771–783, 2009.
We formalize problems of finding large approximately-matching regions of
two related but not completely isomorphic quadrilateral meshes, show
that these problems are NP-complete, and describe a natural greedy
heuristic that is guaranteed to find good matches when the mismatching
parts of the meshes are small.

(Preprint)

**Motorcycle graphs: canonical quad mesh partitioning**.

D. Eppstein,
M. T. Goodrich,
E. Kim,
and R. Tamstorf.

*Proc. 6th Symp. Geometry Processing*, Copenhagen, Denmark, 2008.

*Computer Graphics Forum* 27 (5): 1477–1486, 2008.
We use a construction inspired by the motorcycle graphs previously used
in straight skeleton construction, to partition quadrilateral meshes
into a small number of structured submeshes. Our construction is
canonical in that two copies of the same mesh will always be partitioned
in the same way, and can be used to speed up graph isomorphism
computations for geometric models in feature animation.

Co-authors –
Publications –
David Eppstein –
Theory Group –
Inf. & Comp. Sci. –
UC Irvine

Semi-automatically filtered
from a common source file.