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

DOI10.1016/j.endm.2015.07.042zbMath1347.05128arXiv1506.08750OpenAlexW1735246627MaRDI QIDQ5890935

Mario Valencia-Pabon, Guillermo Durán, Bernard Ries, María Pía Mazzoleni, Liliana Alcón, Marisa Gutierrez, Flavia Bonomo-Braberman

Publication date: 17 October 2016

Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

forbidden induced subgraphsedge intersection graphsHelly circular-arc graphsnormal circular-arc graphspaths on a grid

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (2)

Edge-intersection graphs of boundary-generated paths in a grid ⋮ On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid

Cites Work

• 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
• Normal Helly circular-arc graphs and its subclasses
• Structural results on circular-arc graphs and circle graphs: a survey and the main open problems
• Approximation Algorithms for B 1-EPG Graphs
• Edge intersection graphs of single bend paths on a grid
• Algorithms on circular-arc graphs
• Characterizing circular-arc graphs
• Unnamed Item
• Unnamed Item

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