Proper Helly Circular-Arc Graphs

DOI10.1007/978-3-540-74839-7_24MaRDI QIDQ3508572zbMATH OpenOpenAlexFDO

Authors Min Chih Lin, Francisco J. Soulignac, Jayme L. 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 algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Graph representations (geometric and intersection representations, etc.) (05C62)

Recommendations

• Characterizations and Linear Time Recognition of Helly Circular-Arc Graphs
• Linear-time recognition of Helly circular-arc models and graphs
• Normal Helly circular-arc graphs and its subclasses
• On cliques of Helly Circular-arc Graphs
• Characterizations and recognition of circular-arc graphs and subclasses: a survey

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• A Simpler Linear-Time Recognition of Circular-Arc Graphs
• A certifying algorithm for the consecutive-ones property
• Certifying Algorithms for Recognizing Proper Circular-Arc Graphs and Unit Circular-Arc Graphs
• Efficient construction of unit circular-arc models
• Efficient graph representations
• Graph Classes: A Survey
• 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
• Matrix characterizations of circular-arc graphs
• On cliques of Helly Circular-arc Graphs
• Structure theorems for some circular-arc graphs

Cited in

(21)

• On cliques of Helly Circular-arc Graphs
• Characterizations and recognition of circular-arc graphs and subclasses: a survey
• Extending partial representations of circular-arc graphs
• Certifying algorithms
• Hadwiger's conjecture for proper circular arc graphs
• Structural results on circular-arc graphs and circle graphs: a survey and the main open problems
• On some subclasses of circular-arc graphs
• Certifying Algorithms for Recognizing Proper Circular-Arc Graphs and Unit Circular-Arc Graphs
• Completing colored graphs to meet a target property
• Diamond-free circle graphs are Helly circle
• Modification problems toward proper (Helly) circular-arc graphs
• Essential obstacles to Helly circular-arc graphs
• Characterizations and Linear Time Recognition of Helly Circular-Arc Graphs
• Linear-time recognition of Helly circular-arc models and graphs
• A Simple Linear Time Algorithm for the Isomorphism Problem on Proper Circular-Arc Graphs
• From a Circular-Arc Model to a Proper Circular-Arc Model
• The clique operator on circular-arc graphs
• Subclasses of circular-arc bigraphs: Helly, normal and proper
• Normal Helly circular-arc graphs and its subclasses
• Proper circular arc graphs as intersection graphs of paths on a grid
• scientific article; zbMATH DE number 6679164 (Why is no real title available?)

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

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