Characterizations and recognition of circular-arc graphs and subclasses: a survey
From MaRDI portal
Publication:1045049
Recommendations
- Linear-time recognition of circular-arc graphs
- Characterizations and Linear Time Recognition of Helly Circular-Arc Graphs
- Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
- Proper Helly Circular-Arc Graphs
- Linear-time recognition of Helly circular-arc models and graphs
Cites work
- scientific article; zbMATH DE number 437537 (Why is no real title available?)
- scientific article; zbMATH DE number 3908482 (Why is no real title available?)
- scientific article; zbMATH DE number 3706451 (Why is no real title available?)
- scientific article; zbMATH DE number 53952 (Why is no real title available?)
- scientific article; zbMATH DE number 3608050 (Why is no real title available?)
- scientific article; zbMATH DE number 403948 (Why is no real title available?)
- scientific article; zbMATH DE number 3307330 (Why is no real title available?)
- scientific article; zbMATH DE number 3342041 (Why is no real title available?)
- scientific article; zbMATH DE number 3064989 (Why is no real title available?)
- $O(M\cdot N)$ Algorithms for the Recognition and Isomorphism Problems on Circular-Arc Graphs
- A Characterization of Comparability Graphs and of Interval Graphs
- A Simple Test for the Consecutive Ones Property
- A Simpler Linear-Time Recognition of Circular-Arc Graphs
- A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular-arc graphs, and nested interval graphs
- A structure theorem for the consecutive 1's property
- Algorithmic graph theory and perfect graphs
- Algorithms for clique-independent sets on subclasses of circular-arc graphs
- Algorithms for finding clique-transversals of graphs
- Algorithms on circular-arc graphs
- An Efficient Test for Circular-Arc Graphs
- An approximation result for a periodic allocation problem
- Bipartite permutation graphs
- Certifying Algorithms for Recognizing Proper Circular-Arc Graphs and Unit Circular-Arc Graphs
- Certifying LexBFS Recognition Algorithms for Proper Interval Graphs and Proper Interval Bigraphs
- Characterization problems for graphs, partially ordered sets, lattices, and families of sets
- Characterizations and Linear Time Recognition of Helly Circular-Arc Graphs
- Characterizing circular-arc graphs
- Circular-arc graphs with clique cover number two
- Circular‐arc digraphs: A characterization
- Efficient construction of unit circular-arc models
- Efficient graph representations
- Graph Classes: A Survey
- Interval bigraphs and circular arc graphs
- Interval digraphs: An analogue of interval graphs
- Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
- 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
- Linear-time recognition of Helly circular-arc models and graphs
- Linear-time recognition of circular-arc graphs
- List homomorphisms and circular arc graphs
- Matrix characterizations of circular-arc graphs
- Modular decomposition and transitive orientation
- On chordal proper circular arc graphs
- On cliques of Helly Circular-arc Graphs
- On some subclasses of circular-arc graphs
- On the 2-Chain Subgraph Cover and Related Problems
- On the Ferrers dimension of a digraph
- On the structure of local tournaments
- PC trees and circular-ones arrangements.
- Partial Characterizations of Circular-Arc Graphs
- Polynomial time recognition of unit circular-arc graphs
- Proper Helly Circular-Arc Graphs
- Recognition of Circle Graphs
- Recognizing interval digraphs and interval bigraphs in polynomial time
- Representing digraphs using intervals or circular arcs
- SOME APPLICATIONS OF GRAPH THEORY AND RELATED NON‐METRIC TECHNIQUES TO PROBLEMS OF APPROXIMATE SERIATION: THE CASE OF SYMMETRIC PROXIMITY MEASURES
- Structure theorems for some circular-arc graphs
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Topics in Intersection Graph Theory
- Two remarks on circular arc graphs
- Unit Circular-Arc Graph Representations and Feasible Circulations
Cited in
(41)- On cliques of Helly Circular-arc Graphs
- Extending partial representations of circular-arc graphs
- Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs
- Boxicity of circular arc graphs
- The Vietoris-Rips complexes of a circle
- Structural results on circular-arc graphs and circle graphs: a survey and the main open problems
- Forbidden induced subgraphs of normal Helly circular-arc graphs: characterization and detection
- Cyclic arrangements with minimum modulo \(m\) winding numbers
- The Persistent Homology of Cyclic Graphs
- Proper Helly Circular-Arc Graphs
- On some subclasses of circular-arc graphs
- A constant factor approximation algorithm for boxicity of circular arc graphs
- A simpler linear-time recognition of circular-arc graphs
- A polynomial kernel for proper Helly circular-arc vertex deletion
- Finding intersection models: from chordal to Helly circular-arc graphs
- Essential obstacles to Helly circular-arc graphs
- Graphs and digraphs represented by intervals and circular arcs
- Lexicographic orientation and representation algorithms for comparability graphs, proper circular arc graphs, and proper interval graphs
- A certifying and dynamic algorithm for the recognition of proper circular-arc graphs
- $O(M\cdot N)$ Algorithms for the Recognition and Isomorphism Problems on Circular-Arc Graphs
- Recognition and isomorphism of proper \(H \)-graphs for unicyclic \(H\) in \textit{FPT}-time
- Partial Characterizations of Circular-Arc Graphs
- On the recognition of fuzzy circular interval graphs
- Fully dynamic recognition of proper circular-arc graphs
- Unit ball graphs on geodesic spaces
- Characterization and linear-time detection of minimal obstructions to concave-round graphs and the circular-ones property
- The clique operator on circular-arc graphs
- Subclasses of circular-arc bigraphs: Helly, normal and proper
- Interval routing schemes for circular-arc graphs
- Dual parameterization of weighted coloring
- On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid
- On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid
- Circularly compatible ones, \(D\)-circularity, and proper circular-arc bigraphs
- scientific article; zbMATH DE number 1990726 (Why is no real title available?)
- Normal Helly circular-arc graphs and its subclasses
- Circular-arc graphs with clique cover number two
- Partial characterizations of circular-arc graphs
- Partial characterizations of 1-perfectly orientable graphs
- Canonical representations for circular-arc graphs using flip sets
- Crossing edge minimization in radial outerplanar layered graphs using segment paths
- Two cases of polynomial-time solvability for the coloring problem
This page was built for publication: Characterizations and recognition of circular-arc graphs and subclasses: a survey
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1045049)
