2021/12/21 by Irina Mustata, Mustata, Irina, Martin Pergel +1 · 1 citation
Computer Science · #Computational Complexity (cs.CC) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #cs.CC #cs.CG
paper · pdf · doi:10.48550/arxiv.2201.08498
arxiv created 2021/12/21 · arxiv updated 2022/01/24
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) and string graphs, intersection graphs of arc-connected curves in a plane. We show that the explored graph classes are NP-hard to recognized even when restricted on graphs with arbitrarily large girth, i.e., length of a shortest cycle. As well, 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.