Linear-time recognition of circular-arc graphs

DOI10.1007/S00453-003-1032-7MaRDI QIDQ1424251zbMATH OpenOpenAlexWikidataFDO

Authors R. 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)

Recommendations

• A simpler linear-time recognition of circular-arc graphs
• A Simpler Linear-Time Recognition of Circular-Arc Graphs
• scientific article; zbMATH DE number 437537
• Polynomial time recognition of unit circular-arc graphs
• Linear-time recognition of Helly circular-arc models and graphs
• Characterizations and Linear Time Recognition of Helly Circular-Arc Graphs
• Recognizing circle graphs in polynomial time
• Linear time algorithms on circular-arc graphs
• Direct and Certifying Recognition of Normal Helly Circular-Arc Graphs in Linear Time
• A certifying and dynamic algorithm for the recognition of proper circular-arc graphs

Cited in

(94)

• Characterizations and recognition of circular-arc graphs and subclasses: a survey
• FO model checking on geometric graphs
• List matrix partitions of graphs representing geometric configurations
• Canonical representations for circular-arc graphs using flip sets
• On the recognition of digital circles in linear time
• Reconstructing a graph from its arc incidence graph
• 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
• Avoidable vertices and edges in graphs: existence, characterization, and applications
• Distributed interactive proofs for the recognition of some geometric intersection graph classes
• Subclasses of circular-arc bigraphs: Helly, normal and proper
• 2-nested matrices: towards understanding the structure of circle graphs
• Essential obstacles to Helly circular-arc graphs
• Disconnected cuts in claw-free graphs
• Characterising circular-arc contact \(B_0\)-VPG graphs
• Recognizing generalized transmission graphs of line segments and circular sectors
• Fully dynamic recognition of proper circular-arc graphs
• A linear-time algorithm for paired-domination on circular-arc graphs
• Graphs and digraphs represented by intervals and circular arcs
• On the hyperbolicity constant of circular-arc graphs
• 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
• Algorithms for clique-independent sets on subclasses of circular-arc graphs
• NP-completeness results for edge modification problems
• Solving the path cover problem on circular-arc graphs by using an approximation algorithm
• On the isomorphism problem for Helly circular-arc graphs
• Induced disjoint paths in circular-arc graphs in linear time
• Succinct encodings for families of interval graphs
• Compact representation of interval graphs and circular-arc graphs of bounded degree and chromatic number
• Recognizing threshold tolerance graphs in O(n^2) time
• Interval routing schemes for circular-arc graphs
• SUB-COLORING AND HYPO-COLORING INTERVAL GRAPHS
• Graph classes with structured neighborhoods and algorithmic applications
• Lexicographic orientation algorithms
• scientific article; zbMATH DE number 437537 (Why is no real title available?)
• On partitioning interval graphs into proper interval subgraphs and related problems
• Direct and Certifying Recognition of Normal Helly Circular-Arc Graphs in Linear Time
• Efficient and perfect domination on circular-arc graphs
• Loop Graphs and Asteroidal Sets
• Colouring Some Classes of Perfect Graphs Robustly
• 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
• Partial Characterizations of Circular-Arc Graphs
• Solving the canonical representation and star system problems for proper circular-arc graphs in logspace
• Proper Helly Circular-Arc Graphs
• Pathwidth of Circular-Arc Graphs
• A Simple Linear Time Algorithm for the Isomorphism Problem on Proper Circular-Arc Graphs
• Certifying Algorithms for Recognizing Proper Circular-Arc Graphs and Unit Circular-Arc Graphs
• Partial characterizations of circular-arc graphs
• Graph classes with structured neighborhoods and algorithmic applications
• On the recognition of fuzzy circular interval graphs
• Coloring fuzzy circular interval graphs
• Recognition of Circle Graphs
• scientific article; zbMATH DE number 6829367 (Why is no real title available?)
• O(M\cdot N) Algorithms for the Recognition and Isomorphism Problems on Circular-Arc Graphs
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• A linear time algorithm to recognize circular permutation graphs
• Interval graph representation with given interval and intersection lengths
• Interval-like graphs and digraphs
• Disconnected cuts in claw-free graphs
• FO model checking of geometric graphs
• Bipartite Analogues of Comparability and Cocomparability Graphs
• Min-orderable digraphs
• From a Circular-Arc Model to a Proper Circular-Arc Model
• Powers of cycles, powers of paths, and distance graphs
• Circular-arc bigraphs and its subclasses
• Forbidden structure characterization of circular-arc graphs and a certifying recognition algorithm
• Polynomial time recognition of unit circular-arc graphs
• A Simpler Linear-Time Recognition of Circular-Arc Graphs
• On orthogonal ray graphs
• Extending partial representations of circular-arc graphs
• Maximum max-k-clique subgraphs in cactus subtree graphs
• Linear-time recognition of Helly circular-arc models and graphs
• A simpler linear-time recognition of circular-arc graphs
• A graph-theoretic barcode ordering model for linked-reads
• A polynomial kernel for proper Helly circular-arc vertex deletion
• Computing optimal leaf roots of chordal cographs in linear time
• Simultaneous contact representations of planar graphs
• On coherent configuration of circular-arc graphs
• The complexity of the list homomorphism problem for graphs
• Compact distributed certification of geometric graph classes
• On some subclasses of oriented catch digraphs
• An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs
• A polynomial kernel for proper Helly circular-arc vertex deletion
• A constant factor approximation algorithm for boxicity of circular arc graphs
• On the structure of certain intersection graphs
• Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs
• Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs
• Characterising \((k,\ell )\)-leaf powers
• Obstacle numbers of graphs
• The clique operator on circular-arc graphs
• Recognizing edge clique graphs among interval graphs and probe interval graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1424251)