Edge Intersection Graphs of Paths on a Triangular Grid

2022/03/08 by de Luca, Vitor T. F., Mazzoleni, María Pía, Oliveira, Fabiano S. +2
#05C05 #05C85 #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2203.04250

Abstract

We introduce a new class of intersection graphs, the edge intersection graphs of paths on a triangular grid, called EPGt 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 EPGt representation in which every path has at most k bends is called a B_k-EPGt representation and the corresponding graphs are called B_k-EPGt graphs. We provide examples of B₂-EPG graphs that are B₁-EPGt. We characterize the representation of cliques with three vertices and chordless 4-cycles in B₁-EPGt representations. We also prove that B₁-EPGt graphs have Strong Helly number 3. Furthermore, we prove that B₁-EPGt graphs are 7-clique colorable.

Related

• Computing maximum cliques in B₂-EPG graphs
• Bend-Bounded Path Intersection Graphs: Sausages, Noodles, and Waffles on\n a Grill
• Vertex intersection graphs of paths on a grid: characterization within block graphs
• Edge-intersection graphs of grid paths: the bend-number
• CPG graphs: Some structural and hardness results