Polynomial time recognition of unit circular-arc graphs

DOI10.1016/j.jalgor.2004.08.003zbMath1093.68071OpenAlexW2138933466MaRDI QIDQ5468870

Agustín Gravano, Guillermo Durán, Jeremy P. Spinrad, Ross M. McConnell, Alan C. Tucker

Publication date: 28 April 2006

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/10533/177861

zbMATH Keywords

Graph algorithmsCircular-arc graphsPolynomial recognitionProper circular-arc graphsUnit circular-arc graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (13)

Circular‐Arc Bigraphs and Its Subclasses ⋮ Partial Characterizations of Circular-Arc Graphs ⋮ Partial characterizations of circle graphs ⋮ Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. Chapter I: theory ⋮ Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. Chapter II: algorithms ⋮ Structural results on circular-arc graphs and circle graphs: a survey and the main open problems ⋮ Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs ⋮ Obstacle numbers of graphs ⋮ NP-completeness results for edge modification problems ⋮ Completing colored graphs to meet a target property ⋮ Unnamed Item ⋮ Partial characterizations of circular-arc graphs ⋮ Characterizations and recognition of circular-arc graphs and subclasses: a survey

This page was built for publication: Polynomial time recognition of unit circular-arc graphs