Vertex intersection graphs of paths on a grid: characterization within block graphs

2015/10/30 by Alcón, L., Bonomo, F., Mazzoleni, M. P.
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1510.09174

Abstract

We investigate graphs that can be represented as vertex intersections of horizontal and vertical paths in a grid, the so called B₀-VPG graphs. Recognizing this class is an NP-complete problem. Although, there exists a polynomial time algorithm for recognizing chordal B₀-VPG graphs. In this paper, we present a minimal forbidden induced subgraph characterization of B₀-VPG graphs restricted to block graphs. As a byproduct, the proof of the main theorem provides an alternative certifying recognition and representation algorithm for B₀-VPG graphs in the class of block graphs.

Related

• Bend-Bounded Path Intersection Graphs: Sausages, Noodles, and Waffles on\n a Grill
• Edge Intersection Graphs of Paths on a Triangular Grid
• B₀-VPG Representation of AT-free Outerplanar Graphs
• CPG graphs: Some structural and hardness results
• Unit Grid Intersection Graphs: Recognition and Properties