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,
doi:10.1145/167088.167159.
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, doi:10.1006/jcss.1996.0002
(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,
doi:10.1137/S0097539794269072.
Second half of journal version of Separator based sparsification for dynamic planar graph algorithms.