On unit grid intersection graphs and several other intersection graph classes

Abstract

We explore what could make recognition of particular intersection-defined classes hard. We focus mainly on unit grid intersection graphs (UGIGs), i.e., intersection graphs of unit-length axis-aligned segments and grid intersection graphs (GIGs, which are defined like UGIGs without unit-length restriction). As side effects we obtain several further nontrivial results.
We show that the explored graph classes are NP-hard to recognized even when restricted to graphs with arbitrarily large girth, i.e., length of a shortest cycle. Next we show that the recognition of these classes remains hard even for graphs with restricted degree (4, 5 and 8 depending on a particular class). For UGIGs we present structural results on the size of a possible representation, too.