On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid
From MaRDI portal
Publication:5915780
DOI10.1016/j.dam.2016.08.004zbMath1441.05121OpenAlexW2769000666MaRDI QIDQ5915780
Flavia Bonomo-Braberman, Guillermo Durán, María Pía Mazzoleni, Mario Valencia-Pabon, Liliana Alcón, Marisa Gutierrez, Bernard Ries
Publication date: 20 December 2017
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/11336/83118
forbidden induced subgraphsedge intersection graphspowers of cyclespaths on a gridnormal, Helly circular-arc graphs
Paths and cycles (05C38) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Related Items
CPG graphs: some structural and hardness results ⋮ Hardness and approximation for L-EPG and \(B_1\)-EPG graphs ⋮ Proper circular arc graphs as intersection graphs of paths on a grid ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Forbidden induced subgraphs of normal Helly circular-arc graphs: characterization and detection
- On the bend-number of planar and outerplanar graphs
- Some properties of edge intersection graphs of single-bend paths on a grid
- Edge intersection graphs of systems of paths on a grid with a bounded number of bends
- Characterizations and recognition of circular-arc graphs and subclasses: a survey
- A tree representation for \(P_ 4\)-sparse graphs
- Normal Helly circular-arc graphs and its subclasses
- Edge-intersection graphs of grid paths: the bend-number
- Structural results on circular-arc graphs and circle graphs: a survey and the main open problems
- 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”
- Approximation Algorithms for B 1-EPG Graphs
- Edge intersection graphs of single bend paths on a grid
- Characterizations and Linear Time Recognition of Helly Circular-Arc Graphs
- Stability in circular arc graphs
- Algorithms on circular-arc graphs
- Forbidden structure characterization of circular-arc graphs and a certifying recognition algorithm
- Characterizing circular-arc graphs
- On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid
