On the intersection graphs of orthogonal line segments in the plane: characterizations of some subclasses of chordal graphs

DOI10.1007/s00373-012-1133-7zbMath1267.05216OpenAlexW2052532226MaRDI QIDQ2376078

Martin Charles Golumbic, Bernard Ries

Publication date: 26 June 2013

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

Full work available at URL: https://doi.org/10.1007/s00373-012-1133-7

zbMATH Keywords

rectangular gridsplit graphssegment graphs2-DIR graphschordal bull-free graphschordal claw-free graphsvertex intersection graph

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75)

Related Items (11)

Vertex intersection graphs of paths on a grid: characterization within block graphs ⋮ 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 ⋮ Posets and VPG graphs ⋮ Characterizations of cographs as intersection graphs of paths on a grid ⋮ On some special classes of contact \(B_0\)-VPG graphs ⋮ Recognizing Some Subclasses of Vertex Intersection Graphs of 0-Bend Paths in a Grid ⋮ 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

• Unnamed Item
• Unnamed Item
• Some properties of edge intersection graphs of single-bend paths on a grid
• Grid intersection graphs and boxicity
• The splittance of a graph
• On grid intersection graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Intersection graphs of segments
• Efficient graph representations
• Algorithmic graph theory and perfect graphs
• Recognizing bull-free perfect graphs
• String graphs of k-bend paths on a grid
• Edge intersection graphs of single bend paths on a grid
• Recognizing Some Subclasses of Vertex Intersection Graphs of 0-Bend Paths in a Grid
• Representation of a finite graph by a set of intervals on the real line
• Topics in Intersection Graph Theory
• Asteroidal Triple-Free Graphs

This page was built for publication: On the intersection graphs of orthogonal line segments in the plane: characterizations of some subclasses of chordal graphs