scientific article

DOI10.23638/DMTCS-22-1-19zbMath1454.05059arXiv1906.11185MaRDI QIDQ3386616

Uéverton S. Souza, Claudson F. Bornstein, Tanilson D. Santos, Martin Charles Golumbic, Jayme Luiz Szwarcfiter

Publication date: 5 January 2021

Full work available at URL: https://arxiv.org/abs/1906.11185

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

pathsNP-completenessintersection graphsgridHellyEPGsingle bend

Mathematics Subject Classification ID

Paths and cycles (05C38)

Related Items (1)

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

Cites Work

• Edge intersection graphs of \(L\)-shaped paths in grids
• On the bend-number of planar and outerplanar graphs
• 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
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Complexity aspects of the Helly property: graphs and hypergraphs
• 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
• Minimum-weight triangulation is NP-hard
• On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: