Bend-Bounded Path Intersection Graphs: Sausages, Noodles, and Waffles on a Grill

2012/06/22 by Chaplick, Steven, Jelínek, Vít, Kratochvíl, Jan +1
#Combinatorics (math.CO) #Computational Geometry (cs.CG) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1206.5159

Abstract

In this paper we study properties of intersection graphs of k-bend paths in the rectangular grid. A k-bend path is a path with at most k 90 degree turns. The class of graphs representable by intersections of k-bend paths is denoted by B_k-VPG. We show here that for every fixed k, B_k-VPG is a proper subset of B_k+1-VPG and that recognition of graphs from B_k-VPG is NP-complete even when the input graph is given by a B_k+1-VPG representation. We also show that the class B_k-VPG (for k>0) is in no inclusion relation with the class of intersection graphs of straight line segments in the plane.

Related

• Edge-intersection graphs of grid paths: the bend-number
• Vertex intersection graphs of paths on a grid: characterization within block graphs
• B₀-VPG Representation of AT-free Outerplanar Graphs
• CPG graphs: Some structural and hardness results
• Intersection Graphs of L-Shapes and Segments in the Plane