On unit grid intersection graphs and several other intersection graph classes
Main Article Content
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.
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.
Article Details
How to Cite
Mustaţă, I., & Pergel, M.
(2019).
On unit grid intersection graphs and several other intersection graph classes.
Acta Mathematica Universitatis Comenianae, 88(3), 967-972.
Retrieved from http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1202/749
Issue
Section
EUROCOMB 2019