A Separator Theorem for Planar Graphs

Richard J. Lipton; Robert Endre Tarjan

doi:10.1137/0136016

journal article Apr 01, 1979

A Separator Theorem for Planar Graphs

Richard J. Lipton Robert Endre Tarjan

SIAM Journal on Applied Mathematics Vol. 36 No. 2 pp. 177-189 · Society for Industrial & Applied Mathematics (SIAM)

View at Publisher Save 10.1137/0136016

Topics

No keywords indexed for this article. Browse by subject →

References

14

[1]

Aho Alfred V. (1975)

[2]

10.1137/0205015

[3]

Erdo˝s P. (1975)

[4]

10.1137/0710032

[5]

Hall Dick Wick (1955)

[6]

GRAPH THEORY

Frank Harary

1969 10.21236/ad0705364

[7]

10.1145/322003.322015

[8]

10.1145/362248.362272

[9]

Efficient Planarity Testing

John Hopcroft, Robert Tarjan

Journal of the ACM 10.1145/321850.321852

[10]

Knuth Donald E. (1973)

[11]

Sur le problème des courbes gauches en Topologie

Casimir Kuratowski

Fundamenta Mathematicae 1930 10.4064/fm-15-1-271-283

[12]

10.1145/321978.321990

[13]

10.1016/s0022-0000(72)80017-5

[14]

10.1007/bf01683275

Cited By

879

Divide-and-Conquer: Scalable Shortest Path Counting on Large Road Networks

Muhammad Farhan, Henning Koehler · 2025

Proceedings of the ACM on Managemen...

Gap sets for the spectra of cubic graphs

Alicia Kollár, Peter Sarnak · 2021

Communications of the American Math...

Fast counting with tensor networks

Stefanos Kourtis, Claudio Chamon · 2019

SciPost Physics

All-Pairs Shortest Path algorithms for planar graph for GPU-accelerated clusters

Hristo Djidjev, Guillaume Chapuis · 2015

Journal of Parallel and Distributed...

A partial k-arboretum of graphs with bounded treewidth

Hans L. Bodlaender · 1998

Theoretical Computer Science

A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs

George Karypis, Vipin Kumar · 1998

SIAM Journal on Scientific Computin...

Finding good approximate vertex and edge partitions is NP-hard

Thang Nguyen Bui, Curt Jones · 1992

Information Processing Letters

Metrics

879

Citations

14

References

Details

Published: Apr 01, 1979
Vol/Issue: 36(2)
Pages: 177-189

Authors

Cite This Article

Richard J. Lipton, Robert Endre Tarjan (1979). A Separator Theorem for Planar Graphs. SIAM Journal on Applied Mathematics, 36(2), 177-189. https://doi.org/10.1137/0136016

A Separator Theorem for Planar Graphs

You May Also Like