| Article ID: | iaor19951085 |
| Country: | Netherlands |
| Volume: | 52 |
| Issue: | 3 |
| Start Page Number: | 233 |
| End Page Number: | 252 |
| Publication Date: | Aug 1994 |
| Journal: | Discrete Applied Mathematics |
| Authors: | Kratochvl Jan |
The paper introduces a weaker but still NP-complete satisfiability problem to prove NP-completeness of recognizing several classes of intersection graphs of geometric objects in the plane, including grid intersection graphs and graphs of boxicity two.