Lichtenstein, David Planar formulae and their uses. (English) Zbl 0478.68043 SIAM J. Comput. 11, 329-343 (1982). Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page Cited in 4 ReviewsCited in 190 Documents MSC: 68Q25 Analysis of algorithms and problem complexity 68R10 Graph theory (including graph drawing) in computer science 03D15 Complexity of computation (including implicit computational complexity) 03B10 Classical first-order logic Keywords:planar Boolean formulae; planar node cover; planar Hamiltonian circuit; geometric connected dominating set; planar generalized geography; NP- completeness; P-space-completeness; combinatorial games; planar graphs PDF BibTeX XML Cite \textit{D. Lichtenstein}, SIAM J. Comput. 11, 329--343 (1982; Zbl 0478.68043) Full Text: DOI