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

DOI10.1007/s00373-017-1791-6zbMath1371.05186arXiv1510.09174OpenAlexW2964098469MaRDI QIDQ2409505

María Pía Mazzoleni, Liliana Alcón, Flavia Bonomo-Braberman

Publication date: 11 October 2017

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1510.09174

zbMATH Keywords

forbidden induced subgraphsblock graphspaths on a gridvertex intersection graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62) Graph designs and isomorphic decomposition (05C51)

Related Items (8)

CPG graphs: some structural and hardness results ⋮ Characterising circular-arc contact \(B_0\)-VPG graphs ⋮ \(B_0\)-VPG representation of AT-free outerplanar graphs ⋮ B0-VPG Representation of AT-free Outerplanar Graphs ⋮ On contact graphs of paths on a grid ⋮ On some special classes of contact \(B_0\)-VPG graphs ⋮ Characterization of \(\mathrm{B}_0\)-VPG cocomparability graphs and a 2D visualization of their posets ⋮ Characterization and a 2D Visualization of B$$_{0}$$-VPG Cocomparability Graphs

Cites Work

• Intersection graphs of segments
• On the intersection graphs of orthogonal line segments in the plane: characterizations of some subclasses of chordal graphs
• Recognizing Some Subclasses of Vertex Intersection Graphs of 0-Bend Paths in a Grid
• Vertex Intersection Graphs of Paths on a Grid
• Topology of Thin Film RC Circuits
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Vertex intersection graphs of paths on a grid: characterization within block graphs