Proper circular arc graphs as intersection graphs of paths ton a grid

ESTHER GALBY; MARÍA PÍA MAZZOLENI; BERNARD RIES

Mendoza

Congreso; Reunión Anual de la UMA junto a la SOMACHI (SUMA 2019); 2019

Golumbic et al. introduced the class of eextit{dge intersection graphs of paths on a grid} (extit{EPG graphs}), i.e. graphs for whichthere exists a collection of nontrivial paths on a rectangular grid in one-to-one correspondence with their vertex set, suchthat two vertices are adjacent if and only if the corresponding paths share at least one edge of the grid, and showed thatevery graph is in fact an EPG graph. A natural restriction which was thereupon considered, suggests to limit the number ofbends (i.e. $90^{circ}$ turns at a grid-point) that a path may have; for $kgeq 0$, the class extit{$B_k$-EPG} consists of those EPG graphs admittinga representation in which each path has at most $k$ bends.A extit{circular arc graph} (extit{CA} graph) is an intersection graph of open arcs on a circle, i.e. a graph $G = (V, E)$ is a circular arc graph if one can associate an open arc on a circle with each vertex such that two vertices are adjacent if and only if theircorresponding arcs intersect. If $C$ denotes the corresponding circle and $A$ the corresponding set of arcs, then $R = (C, A)$ iscalled a circular arc representation of $G$. A circular arc graph having a circular arc representation where noarc properly contains another is called a extit{proper circular arc graph} (extit{PCA} graph). In this paper, we present a characterization by an infinite family of minimal forbiddeninduced subgraphs, of proper circular arc graphs which are intersection graphs of pathson a grid, where each path has at most one bend. That is, we present a characterization by an infinite family of minimal forbidden induced subgraphs for $B_1-EPGcap PCA$. This is a first step towards finding a characterization of the minimal graphs in ($CAcap B_2-EPG$) $smallsetminus$ ($CAcap B_1-EPG$).