On Interval Graphs Represented as Intersections of Unit-Length Paths in the Shape of ⌞

The EPG graphs represent the class of edge-intersection graphs of paths on a grid. The study of these graphs began in 2009, and since then, several results have been obtained regarding the complexity of recognizing their subclasses. The ⌞-EPG graphs constitute a subclass of EPG graphs, in which each path can only assume the format of “⌞”, in addition to the segments “−” and “|”. The complexity of recognizing this subclass has been shown to be NP-complete [Cameron et al., 2016]. The unit ⌞-EPG graphs constitute a subclass of the ⌞-EPG graphs, where all segments of the paths have a unique size. In this article, besides defining the class of unit ⌞-EPG graphs, we focus on the interval graphs class, for which we provide a characterization by forbidden subgraphs for interval graphs that are unit ⌞-EPG.