What Makes the Recognition Problem Hard for Classes Related to Segment and String graphs?

Irina Mustata, Martin Pergel

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-…