Characterizations of cographs as intersection graphs of paths on a grid

DOI10.1016/j.dam.2014.06.020zbMath1300.05267OpenAlexW1968297533MaRDI QIDQ741533

Bernard Ries, Elad Cohen, Martin Charles Golumbic

Publication date: 12 September 2014

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2014.06.020

zbMATH Keywords

intersection graphinduced subgraphgridcographcotree

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75)

Related Items

Hardness and approximation for L-EPG and \(B_1\)-EPG graphs ⋮ Proper circular arc graphs as intersection graphs of paths on a grid ⋮ Characterising circular-arc contact \(B_0\)-VPG graphs ⋮ Edge-intersection graphs of boundary-generated paths in a grid ⋮ Unnamed Item ⋮ On contact graphs of paths on a grid ⋮ Posets and VPG graphs ⋮ 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

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Edge contractions in subclasses of chordal graphs
• On the bend-number of planar and outerplanar graphs
• Some properties of edge intersection graphs of single-bend paths on a grid
• Edge intersection graphs of systems of paths on a grid with a bounded number of bends
• Complement reducible graphs
• A special planar satisfiability problem and a consequence of its NP- completeness
• A simple linear time algorithm for cograph recognition
• On the intersection graphs of orthogonal line segments in the plane: characterizations of some subclasses of chordal graphs
• Edge-intersection graphs of grid paths: the bend-number
• Edge intersection graphs of single bend paths on a grid
• Recognizing Some Subclasses of Vertex Intersection Graphs of 0-Bend Paths in a Grid
• Vertex Intersection Graphs of Paths on a Grid
• A Simple Linear Time LexBFS Cograph Recognition Algorithm
• A Linear Recognition Algorithm for Cographs
• Planar Graphs as VPG-Graphs
• Induced subgraphs and well‐quasi‐ordering