String graphs of k-bend paths on a grid

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

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

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 (3)

• VPG and EPG bend-numbers of Halin graphs
• Recognizing Some Subclasses of Vertex Intersection Graphs of 0-Bend Paths in a Grid
• 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)