Tree–cotree decomposition
Maintenance of a minimum spanning forest in a dynamic plane graph.
D. Eppstein,
G.F. Italiano,
R. Tamassia,
R.E. Tarjan,
J. Westbrook,
and M. Yung.
1st ACM-SIAM Symp. Discrete Algorithms,
San Francisco, 1990, pp. 1–11.
J. Algorithms 13 (1): 33–54, 1992
(special issue for 1st Symp. Discrete Algorithms).
Corrigendum, J. Algorithms 15: 173, 1993.
The complement of a minimum spanning tree is a maximum spanning tree in the dual graph. By applying this fact we can use a modified form of Sleator and Tarjan's dynamic tree data structure to update the MST in logarithmic time per update.
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.
Curvature-aware fundamental cycles.
P. Diaz-Gutierrez,
D. Eppstein, and
M. Gopi.
17th Pacific Conf. Computer Graphics and Applications, Jeju, Korea,
2009.
Computer
Graphics Forum 28 (7): 2015–2024, 2009.
Considers heuristic modifications to the tree-cotree decomposition of my earlier paper Dynamic generators of topologically embedded graphs, to make the set of fundamental cycles found as part of the decomposition follow the contours of a given geometric model.
On the biplanarity of blowups.
D. Eppstein.
arXiv:2301.09246.
Proc. 31st Int. Symp. Graph Drawing and Network Visualization, Palermo, Italy, 2023 (best paper award).
Springer, Lecture Notes in Computer Science 14465 (part I), pp. 3–17.
J. Graph Algorithms &
Applications 28 (2): 83–99, 2024.
Expanding every vertex of a planar graph to two independent copies can produce a graph of thickness greater than two, disproving a conjecture of Ellen Gethner. We also investigate special cases of this construction for which the thickness is two, such as the graphs whose edges can be decomposed into a path and a dual path.