Linear-time recognition of Helly circular-arc models and graphs

DOI10.1007/s00453-009-9304-5zbMath1209.68376OpenAlexW2156334902WikidataQ60307433 ScholiaQ60307433MaRDI QIDQ627542

Jeremy P. Spinrad, Ross M. McConnell, Benson L. Joeris, Min Chih Lin, Jayme Luiz Szwarcfiter

Publication date: 2 March 2011

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-009-9304-5

zbMATH Keywords

algorithmsforbidden subgraphscircular-arc graphsHelly circular-arc graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (14)

The Persistent Homology of Cyclic Graphs ⋮ From a Circular-Arc Model to a Proper Circular-Arc Model ⋮ On neighborhood-Helly graphs ⋮ Essential obstacles to Helly circular-arc graphs ⋮ Extending partial representations of circular-arc graphs ⋮ Proper Helly Circular-Arc Graphs ⋮ Normal Helly circular-arc graphs and its subclasses ⋮ Structural results on circular-arc graphs and circle graphs: a survey and the main open problems ⋮ Algorithms for finding clique-transversals of graphs ⋮ A linear-time algorithm for clique-coloring problem in circular-arc graphs ⋮ Unnamed Item ⋮ Canonical representations for circular-arc graphs using flip sets ⋮ Characterizations and recognition of circular-arc graphs and subclasses: a survey ⋮ On the isomorphism problem for Helly circular-arc graphs

Cites Work

• Unnamed Item
• A linear-time algorithm for a special case of disjoint set union
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Efficient graph representations
• Linear-time recognition of circular-arc graphs
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• Algorithmic graph theory and perfect graphs
• Representation of a finite graph by a set of intervals on the real line
• Certifying Algorithms for Recognizing Proper Circular-Arc Graphs and Unit Circular-Arc Graphs
• Efficient construction of unit circular-arc models
• Characterizations and Linear Time Recognition of Helly Circular-Arc Graphs
• Unit Circular-Arc Graph Representations and Feasible Circulations
• An Efficient Test for Circular-Arc Graphs
• Algorithms on circular-arc graphs
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• Characterizing circular-arc graphs

This page was built for publication: Linear-time recognition of Helly circular-arc models and graphs