Characterizations and Linear Time Recognition of Helly Circular-Arc Graphs

DOI10.1007/11809678_10zbMath1162.05360OpenAlexW1549989156MaRDI QIDQ3591328

Min Chih Lin, Jayme Luiz Szwarcfiter

Publication date: 10 September 2007

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11809678_10

zbMATH Keywords

algorithmsforbidden subgraphscircular-arc graphsHelly circular-arc graphs

Mathematics Subject Classification ID

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

Related Items (12)

Subclasses of circular-arc bigraphs: Helly, normal and proper ⋮ Essential obstacles to Helly circular-arc graphs ⋮ On some graph classes related to perfect graphs: a survey ⋮ Extending partial representations of circular-arc graphs ⋮ Linear-time recognition of Helly circular-arc models and graphs ⋮ Normal Helly circular-arc graphs and its subclasses ⋮ A simpler linear-time recognition of circular-arc graphs ⋮ Structural results on circular-arc graphs and circle graphs: a survey and the main open problems ⋮ Algorithms for finding clique-transversals of graphs ⋮ On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid ⋮ Clique-Coloring Circular-Arc Graphs ⋮ Characterizations and recognition of circular-arc graphs and subclasses: a survey

This page was built for publication: Characterizations and Linear Time Recognition of Helly Circular-Arc Graphs