Linear-time recognition of circular-arc graphs

DOI10.1007/s00453-003-1032-7zbMath1060.68088OpenAlexW2132816737WikidataQ60307434 ScholiaQ60307434MaRDI QIDQ1424251

Ross M. McConnell

Publication date: 11 March 2004

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-003-1032-7

zbMATH Keywords

intersection graphinterval graphtransitive orientation

Mathematics Subject Classification ID

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

Related Items (73)

Subclasses of circular-arc bigraphs: Helly, normal and proper ⋮ FO model checking on geometric graphs ⋮ Induced disjoint paths in circular-arc graphs in linear time ⋮ On partitioning interval graphs into proper interval subgraphs and related problems ⋮ On the structure of certain intersection graphs ⋮ From a Circular-Arc Model to a Proper Circular-Arc Model ⋮ Efficient and perfect domination on circular-arc graphs ⋮ 2-nested matrices: towards understanding the structure of circle graphs ⋮ Forbidden induced subgraphs of normal Helly circular-arc graphs: characterization and detection ⋮ Max point-tolerance graphs ⋮ On recognition of threshold tolerance graphs and their complements ⋮ Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs ⋮ Solving the canonical representation and star system problems for proper circular-arc graphs in logspace ⋮ Essential obstacles to Helly circular-arc graphs ⋮ Circular‐Arc Bigraphs and Its Subclasses ⋮ Succinct encodings for families of interval graphs ⋮ On orthogonal ray graphs ⋮ Extending partial representations of interval graphs ⋮ Recognizing Threshold Tolerance Graphs in $$O(n^2)$$ Time ⋮ Graph classes with structured neighborhoods and algorithmic applications ⋮ Disconnected cuts in claw-free graphs ⋮ Extending partial representations of circular-arc graphs ⋮ On the hyperbolicity constant of circular-arc graphs ⋮ Partial Characterizations of Circular-Arc Graphs ⋮ Compact representation of interval graphs and circular-arc graphs of bounded degree and chromatic number ⋮ Characterising circular-arc contact \(B_0\)-VPG graphs ⋮ Coloring fuzzy circular interval graphs ⋮ Maximum max-k-clique subgraphs in cactus subtree graphs ⋮ Proper Helly Circular-Arc Graphs ⋮ Pathwidth of Circular-Arc Graphs ⋮ Linear-time recognition of Helly circular-arc models and graphs ⋮ A Simple Linear Time Algorithm for the Isomorphism Problem on Proper Circular-Arc Graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Integral mixed unit interval graphs ⋮ Normal Helly circular-arc graphs and its subclasses ⋮ A linear-time algorithm for finding locally connected spanning trees on circular-arc graphs ⋮ A simpler linear-time recognition of circular-arc graphs ⋮ Interval Routing Schemes for Circular-Arc Graphs ⋮ Bipartite Analogues of Comparability and Cocomparability Graphs ⋮ Min-Orderable Digraphs ⋮ Structural results on circular-arc graphs and circle graphs: a survey and the main open problems ⋮ Co-TT graphs and a characterization of split co-TT graphs ⋮ Interval graph representation with given interval and intersection lengths ⋮ List matrix partitions of graphs representing geometric configurations ⋮ Powers of cycles, powers of paths, and distance graphs ⋮ The complexity of the list homomorphism problem for graphs ⋮ Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs ⋮ Characterising \((k,\ell )\)-leaf powers ⋮ Obstacle numbers of graphs ⋮ Algorithms for clique-independent sets on subclasses of circular-arc graphs ⋮ NP-completeness results for edge modification problems ⋮ The clique operator on circular-arc graphs ⋮ An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs ⋮ SUB-COLORING AND HYPO-COLORING INTERVAL GRAPHS ⋮ Recognizing edge clique graphs among interval graphs and probe interval graphs ⋮ Canonical representations for circular-arc graphs using flip sets ⋮ Unnamed Item ⋮ A constant factor approximation algorithm for boxicity of circular arc graphs ⋮ Hardness and structural results for half-squares of restricted tree convex bipartite graphs ⋮ Avoidable vertices and edges in graphs: existence, characterization, and applications ⋮ Linear-Time Recognition of Probe Interval Graphs ⋮ Graph Classes with Structured Neighborhoods and Algorithmic Applications ⋮ Partial characterizations of circular-arc graphs ⋮ Characterizations and recognition of circular-arc graphs and subclasses: a survey ⋮ Lexicographic Orientation Algorithms ⋮ Distributed interactive proofs for the recognition of some geometric intersection graph classes ⋮ Solving the path cover problem on circular-arc graphs by using an approximation algorithm ⋮ Loop Graphs and Asteroidal Sets ⋮ Colouring Some Classes of Perfect Graphs Robustly ⋮ A linear-time algorithm for paired-domination on circular-arc graphs ⋮ On the isomorphism problem for Helly circular-arc graphs ⋮ Graphs and digraphs represented by intervals and circular arcs

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