String graphs of k-bend paths on a grid

DOI10.1016/J.ENDM.2011.05.025MaRDI QIDQ2840697zbMATH OpenOpenAlexFDO

Authors Elad Cohen, Vincent Limouzy, Marina Lipshteyn, Michal Stern, Andrei Asinowski, Martin Charles Golumbic

Publication date 23 July 2013

Published in Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.endm.2011.05.025

zbMATH Keywords

graph coloringchordal graphsHelly propertyplanar graphstriangle-free graphscircle graphsgrid intersection graphsstring graphs

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Structural characterization of families of graphs (05C75)

Recommendations

• Vertex Intersection Graphs of Paths on a Grid
• Bend-Bounded Path Intersection Graphs: Sausages, Noodles, and Waffles on a Grill
• Planar graphs as VPG-graphs
• Planar graphs as VPG-graphs
• 1-string \(B_2\)-VPG representation of planar graphs

Cites work

• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• scientific article; zbMATH DE number 1933269 (Why is no real title available?)
• scientific article; zbMATH DE number 4185548 (Why is no real title available?)
• A special planar satisfiability problem and a consequence of its NP- completeness
• Characterizations of strongly chordal graphs
• Faithful representations of graphs by islands in the extended grid
• Grid intersection graphs and boxicity
• Intersection graphs of curves in the plane
• Intersection graphs of segments
• On grid intersection graphs
• String graphs. I: The number of critical nonstring graphs is infinite
• The Complexity of Coloring Circular Arcs and Chords
• Topology of Thin Film RC Circuits
• Vertex Intersection Graphs of Paths on a Grid

Cited in

(11)

• 1-string B₂-VPG representation of planar graphs
• Helly and strong Helly numbers of B_k-EPG and B_k-VPG graphs
• Planar graphs as VPG-graphs
• Posets and VPG graphs
• Recognizing some subclasses of vertex intersection graphs of 0-bend paths in a grid
• VPG and EPG bend-numbers of Halin graphs
• B0-VPG Representation of AT-free Outerplanar Graphs
• Splitting \(B_2\)-VPG graphs into outer-string and co-comparability graphs
• Planar graphs as VPG-graphs
• 1-string \(B_2\)-VPG representation of planar graphs
• On the intersection graphs of orthogonal line segments in the plane: characterizations of some subclasses of chordal graphs

This page was built for publication: String graphs of \(k\)-bend paths on a grid

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2840697)