A SPECIAL PLANAR SATISFIABILITY PROBLEM AND A CONSEQUENCE OF ITS NP-COMPLETENESS

Authors
KRATOCHVIL J
Citation
J. Kratochvil, A SPECIAL PLANAR SATISFIABILITY PROBLEM AND A CONSEQUENCE OF ITS NP-COMPLETENESS, Discrete applied mathematics, 52(3), 1994, pp. 233-252
Citations number
20
Categorie Soggetti
Mathematics,Mathematics
Journal title
Discrete applied mathematics → ACNP
Volume
52
Issue
3
Year of publication
1994
Pages
233 - 252
Database
ISI
SICI code
Abstract
We introduce a weaker but still NP-complete satisfiability problem to prove NP-completeness of recognizing several classes of intersection g raphs of geometric objects in the plane, including grid intersection g raphs and graphs of boxicity two.