Edge Intersection Graphs of Paths on a Triangular Grid - Luca, Vitor T. F. de; Mazzoleni, María Pía; Oliveira, Fabiano S.; Szwarcfiter, Jayme L. (Anais do Encontro de Teoria da Computação (ETC), 2022)
We introduce a new class of intersection graphs, the edge intersection graphs of paths on a triangular grid, called EPG t graphs. We compare this new class with 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 B k -EPG t representation and the corresponding graphs are called B k -EPG t graphs. We characterize the representation of cliques with three vertices and chordless 4-cycles in B 1 -EPG t representations.