Publications with Tom Spencer
- 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.
- Separator based sparsification I:
planarity testing and minimum spanning trees.
D. Eppstein, Z. Galil, G.F. Italiano, and T. Spencer.
J. Comp. Sys. Sci. 52: 3–27, 1996 (special issue for 25th STOC).First half of journal version of Separator based sparsification for dynamic planar graph algorithms.
- Separator based sparsification II: edge and vertex connectivity.
D. Eppstein, Z. Galil, G.F. Italiano, and T. Spencer.
Tech. Rep. CS96-13, Univ. Ca' Foscari di Venezia, Oct. 1996.
SIAM J. Computing 28 (1): 341–381, 1999.Second half of journal version of Separator based sparsification for dynamic planar graph algorithms.