Proper Helly Circular-Arc Graphs
From MaRDI portal
Publication:3508572
DOI10.1007/978-3-540-74839-7_24zbMath1141.68539MaRDI QIDQ3508572
Min Chih Lin, Francisco J. Soulignac, Jayme Luiz Szwarcfiter
Publication date: 1 July 2008
Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-74839-7_24
algorithms; forbidden subgraphs; Helly circular-arc graphs; proper circular-arc graphs; unit circular-arc graphs
68R10: Graph theory (including graph drawing) in computer science
05C85: Graph algorithms (graph-theoretic aspects)
05C62: Graph representations (geometric and intersection representations, etc.)
Related Items
From a Circular-Arc Model to a Proper Circular-Arc Model, Extending partial representations of circular-arc graphs, Certifying algorithms, The clique operator on circular-arc graphs, Characterizations and recognition of circular-arc graphs and subclasses: a survey, Normal Helly circular-arc graphs and its subclasses, Completing colored graphs to meet a target property, Subclasses of circular-arc bigraphs: Helly, normal and proper, Essential obstacles to Helly circular-arc graphs, Proper circular arc graphs as intersection graphs of paths on a grid, Structural results on circular-arc graphs and circle graphs: a survey and the main open problems, On cliques of Helly Circular-arc Graphs, A Simple Linear Time Algorithm for the Isomorphism Problem on Proper Circular-Arc Graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Linear-time recognition of Helly circular-arc models and graphs
- Efficient graph representations
- Linear-time recognition of circular-arc graphs
- Matrix characterizations of circular-arc graphs
- Structure theorems for some circular-arc graphs
- On cliques of Helly Circular-arc Graphs
- Certifying Algorithms for Recognizing Proper Circular-Arc Graphs and Unit Circular-Arc Graphs
- Efficient construction of unit circular-arc models
- Graph Classes: A Survey
- Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
- A Simpler Linear-Time Recognition of Circular-Arc Graphs