On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid

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

zbMATH Keywords

forbidden induced subgraphsedge intersection graphspowers of cyclespaths on a gridnormal, Helly circular-arc graphs

Mathematics Subject Classification ID

Paths and cycles (05C38) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (4)

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

This page was built for publication: On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid