Geodesic
On unit grid intersection graphs and several other intersection graph classes
Irina Mustaţă1 ; Martin Pergel2 ; Irina Mustaţă ; Martin Pergel
1Berlin Institute of Technology, Institut für Mathematik, Berlin, Germany
2Department of Software and Computer Science Education (KSVI), Charles University, Prague, Czech Republic
Acta mathematica Universitatis Comenianae, Tome 88 (2019) no. 3, pp. 967-972 
Irina Mustaţă; Martin Pergel; Irina Mustaţă; Martin Pergel. On unit grid intersection graphs and several other intersection graph classes. Acta mathematica Universitatis Comenianae, Tome 88 (2019) no. 3, pp. 967-972. http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a94/
@article{AMUC_2019_88_3_a94,
     author = {Irina Musta\c{t}\u{a} and Martin Pergel and Irina Musta\c{t}\u{a} and Martin Pergel},
     title = { On unit grid intersection graphs and several other intersection graph classes},
     journal = {Acta mathematica Universitatis Comenianae},
     pages = {967--972},
     year = {2019},
     volume = {88},
     number = {3},
     url = {http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a94/}
}
TY  - JOUR
AU  - Irina Mustaţă
AU  - Martin Pergel
AU  - Irina Mustaţă
AU  - Martin Pergel
TI  - On unit grid intersection graphs and several other intersection graph classes
JO  - Acta mathematica Universitatis Comenianae
PY  - 2019
SP  - 967
EP  - 972
VL  - 88
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a94/
ID  - AMUC_2019_88_3_a94
ER  - 
%0 Journal Article
%A Irina Mustaţă
%A Martin Pergel
%A Irina Mustaţă
%A Martin Pergel
%T On unit grid intersection graphs and several other intersection graph classes
%J Acta mathematica Universitatis Comenianae
%D 2019
%P 967-972
%V 88
%N 3
%U http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a94/
%F AMUC_2019_88_3_a94

Voir la notice de l'article provenant de la source Comenius University

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.