# David Eppstein - Publications

##
ACM Symp. Theory of Computing (STOC)

I was on the program committee for the 26th Symposium, 1994,
the 32nd Symposium, 2000, the 35th Symposium, 2003, the 38th Symposium,
2006, and the 41st Symposium, 2009.
The
Hypertext Bibliography Project at MIT
also includes
listings of my STOC papers.

**Separator based sparsification for dynamic planar graph algorithms**.

D. Eppstein,
Z. Galil,
G.F. Italiano, and T. Spencer.

*25th ACM Symp. Theory of Computing,* San Diego, 1993, pp. 208–217.
Replaces portions of a hierarchical separator decomposition with smaller
certificates to achieve fast update times for various dynamic planar graph problems. Applications include finding the *k*
best spanning trees of a planar graph.

**Geometric lower bounds for parametric matroid optimization**.

D. Eppstein.

Tech. Rep. 95-11, ICS, UCI, 1995.

*27th ACM Symp. Theory of Computing,* Las Vegas, 1995, pp. 662–671.

*Disc. Comp. Geom.* 20: 463–476, 1998.
Considers graphs in which edge weights are linear functions of time.
Shows nonlinear lower bounds on the number of different
minimum spanning trees appearing
over time by translation from geometric problem of lower envelopes of line segments.
A matroid generalization has a better lower bound coming from many faces
in line arrangements, and the uniform matroid problem is
equivalent to the geometric *k*-set problem.

Conferences –
Publications –
David Eppstein –
Theory Group –
Inf. & Comp. Sci. –
UC Irvine

Semi-automatically filtered
from a common source file.