Edge Intersection Graphs of Paths on a Triangular Grid

VITOR DE LUCA; MARÍA PÍA MAZZOLENI; FABIANO OLIVEIRA; JAYME SZWARCFITER

Encuentro; VII Encontro de Teoria da Computação; 2022

We introduce a new class of intersection graphs, the edge intersectiongraphs of paths on a triangular grid, called EPGt 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 EPGt representation in which every path has at most k bends is called a Bk-EPGt representation and the corresponding graphs are called Bk-EPGt graphs. We characterize the representation of cliques with three vertices and chordless 4-cycles in B1-EPGt representations.