%A Mustaţă, Irina
%A Pergel, Martin
%D 2019
%T On unit grid intersection graphs and several other intersection graph classes
%K
%X 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.
%U http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1202
%J Acta Mathematica Universitatis Comenianae
%0 Journal Article
%P 967-972%V 88
%N 3
%@ 0862-9544
%8 2019-07-31