Lipton, Richard J.; Tarjan, Robert Endre Applications of a planar separator theorem. (English) Zbl 0456.68077 SIAM J. Comput. 9, 615-627 (1980). Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page Cited in 7 ReviewsCited in 152 Documents MSC: 68R10 Graph theory (including graph drawing) in computer science 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) 68Q25 Analysis of algorithms and problem complexity Keywords:algorithm; Boolean circuit complexity; divide-and-conquer; graph embedding; matching; maximum independent set; pebbling; planar graphs; space-time tradeoffs PDF BibTeX XML Cite \textit{R. J. Lipton} and \textit{R. E. Tarjan}, SIAM J. Comput. 9, 615--627 (1980; Zbl 0456.68077) Full Text: DOI OpenURL