Proper Helly Circular-Arc Graphs

DOI10.1007/978-3-540-74839-7_24zbMath1141.68539OpenAlexW2141154343MaRDI 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

zbMATH Keywords

algorithmsforbidden subgraphsHelly circular-arc graphsproper circular-arc graphsunit circular-arc graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (13)

Subclasses of circular-arc bigraphs: Helly, normal and proper ⋮ From a Circular-Arc Model to a Proper Circular-Arc Model ⋮ Essential obstacles to Helly circular-arc graphs ⋮ Proper circular arc graphs as intersection graphs of paths on a grid ⋮ Extending partial representations of circular-arc graphs ⋮ On cliques of Helly Circular-arc Graphs ⋮ A Simple Linear Time Algorithm for the Isomorphism Problem on Proper Circular-Arc Graphs ⋮ Normal Helly circular-arc graphs and its subclasses ⋮ Certifying algorithms ⋮ Structural results on circular-arc graphs and circle graphs: a survey and the main open problems ⋮ The clique operator on circular-arc graphs ⋮ Completing colored graphs to meet a target property ⋮ Characterizations and recognition of circular-arc graphs and subclasses: a survey

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

This page was built for publication: Proper Helly Circular-Arc Graphs