String graphs of k-bend paths on a grid

DOI10.1016/J.ENDM.2011.05.025zbMATH Open1268.05134OpenAlexW2075191511MaRDI QIDQ2840697FDOQ2840697

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

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

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)

Cites Work

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

Cited In (10)

• 1-string \(B_2\)-VPG representation of planar 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)