**Dynamic generators of topologically embedded graphs**.

D. Eppstein.

arXiv:cs.DS/0207082.

*14th ACM-SIAM Symp. Discrete Algorithms,*Baltimore, 2003, pp. 599–608.We describe a decomposition of graphs embedded on 2-dimensional manifolds into three subgraphs: a spanning tree, a dual spanning tree, and a set of leftover edges with cardinality determined by the genus of the manifold. This tree-cotree decomposition allows us to find efficient data structures for dynamic graphs (allowing updates that change the surface), better constants in bounded-genus graph separators, and efficient algorithms for tree-decomposition of bounded-genus bounded-diameter graphs.

(BibTeX – SODA talk slides – Citations)

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

Semi-automatically filtered from a common source file.