Characterizations and Clique Coloring of Edge Intersection Graphs on a Triangular Grid

We introduce a new class of intersection graphs, the edge intersection graphs of paths on a triangular grid, called EPG_t graphs. We show similarities and differences from this new class to the well-known class of EPG graphs. A turn of a path at a grid point is called a bend. An EPG_t representation in which every path has at most k bends is called a \(\hbox {B}_k\) ${\text{B}}_k$ -EPG_t representation and the corresponding graphs are called \(\hbox {B}_k\) ${\text{B}}_k$ -EPG_t graphs. We provide examples of \(\hbox {B}_{{2}}\) ${\text{B}}_2$ -EPG graphs that are \(\hbox {B}_{{1}}\) ${\text{B}}_1$ -EPG_t. We characterize the representation of cliques with three vertices and chordless 4-cycles in \(\hbox {B}_{{1}}\) ${\text{B}}_1$ -EPG_t representations. We also prove that \(\hbox {B}_{{1}}\) ${\text{B}}_1$ -EPG_t graphs have Strong Helly number 3. Furthermore, we prove that \(\hbox {B}_{{1}}\) ${\text{B}}_1$ -EPG_t graphs are 7-clique colorable.