A simpler linear-time recognition of circular-arc graphs

DOI10.1007/s00453-010-9432-yzbMath1234.68326OpenAlexW2160399627WikidataQ60307429 ScholiaQ60307429MaRDI QIDQ644807

Yahav Nussbaum, Haim Kaplan

Publication date: 7 November 2011

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-010-9432-y

zbMATH Keywords

intersection graphrecognition algorithmcircular-arc graphcircular-arc modelconsecutive-ones property

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (3)

Induced disjoint paths in circular-arc graphs in linear time ⋮ Forbidden induced subgraphs of normal Helly circular-arc graphs: characterization and detection ⋮ Normal Helly circular-arc graphs and its subclasses

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Circular-arc graphs with clique cover number two
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Modular decomposition and transitive orientation
• Efficient graph representations
• PC trees and circular-ones arrangements.
• Linear-time recognition of circular-arc graphs
• Matrix characterizations of circular-arc graphs
• Characterizations and Linear Time Recognition of Helly Circular-Arc Graphs
• An Efficient Test for Circular-Arc Graphs
• Algorithms on circular-arc graphs
• $O(M\cdot N)$ Algorithms for the Recognition and Isomorphism Problems on Circular-Arc Graphs
• A Simpler Linear-Time Recognition of Circular-Arc Graphs

This page was built for publication: A simpler linear-time recognition of circular-arc graphs