Characterizations and recognition of circular-arc graphs and subclasses: a survey
From MaRDI portal
Publication:1045049
DOI10.1016/j.disc.2008.04.003zbMath1228.05218OpenAlexW2005349020MaRDI QIDQ1045049
Min Chih Lin, Jayme Luiz Szwarcfiter
Publication date: 15 December 2009
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disc.2008.04.003
algorithmscircular-arc graphsHelly circular-arc graphsproper circular-arc graphsco-bipartite circular-arc graphsunit circular-arc graphs
Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)
Related Items
The Vietoris-Rips complexes of a circle ⋮ Subclasses of circular-arc bigraphs: Helly, normal and proper ⋮ The Persistent Homology of Cyclic Graphs ⋮ Forbidden induced subgraphs of normal Helly circular-arc graphs: characterization and detection ⋮ Essential obstacles to Helly circular-arc graphs ⋮ Unit ball graphs on geodesic spaces ⋮ Extending partial representations of circular-arc graphs ⋮ Crossing edge minimization in radial outerplanar layered graphs using segment paths ⋮ On cliques of Helly Circular-arc Graphs ⋮ Finding intersection models: from chordal to Helly circular-arc graphs ⋮ Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs ⋮ Normal Helly circular-arc graphs and its subclasses ⋮ Interval Routing Schemes for Circular-Arc Graphs ⋮ On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid ⋮ Structural results on circular-arc graphs and circle graphs: a survey and the main open problems ⋮ Boxicity of circular arc graphs ⋮ A certifying and dynamic algorithm for the recognition of proper circular-arc graphs ⋮ On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid ⋮ The clique operator on circular-arc graphs ⋮ Two cases of polynomial-time solvability for the coloring problem ⋮ Canonical representations for circular-arc graphs using flip sets ⋮ A constant factor approximation algorithm for boxicity of circular arc graphs ⋮ Dual parameterization of weighted coloring ⋮ Fully dynamic recognition of proper circular-arc graphs ⋮ Partial Characterizations of 1‐Perfectly Orientable Graphs ⋮ Cyclic arrangements with minimum modulo \(m\) winding numbers ⋮ Graphs and digraphs represented by intervals and circular arcs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Linear-time recognition of Helly circular-arc models and graphs
- Two remarks on circular arc graphs
- Algorithms for finding clique-transversals of graphs
- Circular-arc graphs with clique cover number two
- Bipartite permutation graphs
- On the Ferrers dimension of a digraph
- Characterization problems for graphs, partially ordered sets, lattices, and families of sets
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Modular decomposition and transitive orientation
- On chordal proper circular arc graphs
- Recognizing interval digraphs and interval bigraphs in polynomial time
- Efficient graph representations
- PC trees and circular-ones arrangements.
- 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
- On the structure of local tournaments
- Representing digraphs using intervals or circular arcs
- List homomorphisms and circular arc graphs
- Algorithms for clique-independent sets on subclasses of circular-arc graphs
- A structure theorem for the consecutive 1's property
- Matrix characterizations of circular-arc graphs
- Structure theorems for some circular-arc graphs
- A Simple Test for the Consecutive Ones Property
- Partial Characterizations of Circular-Arc Graphs
- On cliques of Helly Circular-arc Graphs
- Proper Helly Circular-Arc Graphs
- 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
- Interval digraphs: An analogue of interval graphs
- An Efficient Test for Circular-Arc Graphs
- A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular-arc graphs, and nested interval graphs
- Algorithms on circular-arc graphs
- Circular‐arc digraphs: A characterization
- Topics in Intersection Graph Theory
- Graph Classes: A Survey
- Recognition of Circle Graphs
- On the 2-Chain Subgraph Cover and Related Problems
- SOME APPLICATIONS OF GRAPH THEORY AND RELATED NON‐METRIC TECHNIQUES TO PROBLEMS OF APPROXIMATE SERIATION: THE CASE OF SYMMETRIC PROXIMITY MEASURES
- Interval bigraphs and circular arc graphs
- $O(M\cdot N)$ Algorithms for the Recognition and Isomorphism Problems on Circular-Arc Graphs
- Lexicographic orientation and representation algorithms for comparability graphs, proper circular arc graphs, and proper interval graphs
- Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
- Certifying LexBFS Recognition Algorithms for Proper Interval Graphs and Proper Interval Bigraphs
- Polynomial time recognition of unit circular-arc graphs
- Characterizing circular-arc graphs
- A Characterization of Comparability Graphs and of Interval Graphs
- A Simpler Linear-Time Recognition of Circular-Arc Graphs
- An approximation result for a periodic allocation problem
