Separator based sparsification. I: Planarity testing and minimum spanning trees

DOI10.1006/jcss.1996.0002zbMath0846.68079OpenAlexW1552413686WikidataQ61609645 ScholiaQ61609645MaRDI QIDQ1915501

Thomas H. Spencer, David Eppstein, Zvi Galil, Giuseppe F. Italiano

Publication date: 16 July 1996

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.1996.0002

zbMATH Keywords

dynamic planar graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05)

Related Items (13)

Maintaining triconnected components under node expansion ⋮ Sublinear separators, fragility and subexponential expansion ⋮ Decomposable multi-parameter matroid optimization problems. ⋮ Optimal decremental connectivity in planar graphs ⋮ Dynamic planar embeddings of dynamic graphs ⋮ Unnamed Item ⋮ Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs. ⋮ Decremental SPQR-trees for Planar Graphs ⋮ Maintaining dynamic minimum spanning trees: an experimental study ⋮ Unnamed Item ⋮ Constant-time dynamic weight approximation for minimum spanning forest ⋮ Single-source shortest paths and strong connectivity in dynamic planar graphs ⋮ Incremental convex planarity testing

This page was built for publication: Separator based sparsification. I: Planarity testing and minimum spanning trees