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.08750MaRDI 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 subgraphs; edge intersection graphs; Helly circular-arc graphs; normal circular-arc graphs; paths on a grid

Mathematics Subject Classification ID

05C38: Paths and cycles

05C85: Graph algorithms (graph-theoretic aspects)

05C62: Graph representations (geometric and intersection representations, etc.)

Related Items

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

Cites Work

• Unnamed Item
• Unnamed Item
• 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