Edge-intersection graphs of boundary-generated paths in a grid

DOI10.1016/j.dam.2017.10.014zbMath1377.05150OpenAlexW2767428423MaRDI QIDQ1693146

Deepak Rajendraprasad, Gila Morgenstern, Martin Charles Golumbic

Publication date: 11 January 2018

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

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

zbMATH Keywords

linear \(k\)-arboricityB1-EPG graphsboundary-generated pathsequivalence covering number

Mathematics Subject Classification ID

Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (1)

Hardness and approximation for L-EPG and \(B_1\)-EPG graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Edge intersection graphs of \(L\)-shaped paths in grids
• VPG and EPG bend-numbers of Halin graphs
• On the bend-number of planar and outerplanar graphs
• Some properties of edge intersection graphs of single-bend paths on a grid
• Characterizations of cographs as intersection graphs of paths on a grid
• Edge intersection graphs of systems of paths on a grid with a bounded number of bends
• Covering graphs by the minimum number of equivalence relations
• On a product dimension of graphs
• Some problems about linear arboricity
• A simple proof of the Galvin-Ramsey property of the class of all finite graphs and a dimension of a graph
• A description of claw-free perfect graphs
• Linear \(k\)-arboricities on trees
• On edge intersection graphs of paths with 2 bends
• Edge-intersection graphs of grid paths: the bend-number
• Single bend paths on a grid have strong helly number 4: errata atque emendationes ad “edge intersection graphs of single bend paths on a grid”
• Edge intersection graphs of single bend paths on a grid
• On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid

This page was built for publication: Edge-intersection graphs of boundary-generated paths in a grid