Characterizations and Linear Time Recognition of Helly Circular-Arc Graphs

DOI10.1007/11809678_10MaRDI QIDQ3591328zbMATH OpenOpenAlexFDO

Authors Min Chih Lin, Jayme L. Szwarcfiter

Publication date 10 September 2007

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11809678_10

zbMATH Keywords

algorithmscircular-arc graphsforbidden subgraphsHelly circular-arc graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Recommendations

• Linear-time recognition of Helly circular-arc models and graphs
• Proper Helly Circular-Arc Graphs
• Direct and Certifying Recognition of Normal Helly Circular-Arc Graphs in Linear Time
• Normal Helly circular-arc graphs and its subclasses
• Forbidden induced subgraphs of normal Helly circular-arc graphs: characterization and detection

Cited in

(25)

• Normal Helly circular-arc graphs and its subclasses
• On the isomorphism problem for Helly circular-arc graphs
• Finding intersection models: from chordal to Helly circular-arc graphs
• Structural results on circular-arc graphs and circle graphs: a survey and the main open problems
• Linear-time recognition of Helly circular-arc models and graphs
• Recognition and isomorphism of proper \(H \)-graphs for unicyclic \(H\) in \textit{FPT}-time
• A Simpler Linear-Time Recognition of Circular-Arc Graphs
• On cliques of Helly Circular-arc Graphs
• Proper Helly Circular-Arc Graphs
• Subclasses of circular-arc bigraphs: Helly, normal and proper
• Direct and Certifying Recognition of Normal Helly Circular-Arc Graphs in Linear Time
• Linear-time recognition of circular-arc graphs
• Clique-coloring circular-arc graphs
• On some graph classes related to perfect graphs: a survey
• Essential obstacles to Helly circular-arc graphs
• Forbidden induced subgraphs of normal Helly circular-arc graphs: characterization and detection
• Diamond-free circle graphs are Helly circle
• Forbidden structure characterization of circular-arc graphs and a certifying recognition algorithm
• On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid
• A simpler linear-time recognition of circular-arc graphs
• Algorithms for finding clique-transversals of graphs
• Characterizations and recognition of circular-arc graphs and subclasses: a survey
• Polynomial time recognition of unit circular-arc graphs
• Extending partial representations of circular-arc graphs
• A polynomial kernel for proper Helly circular-arc vertex deletion

This page was built for publication: Characterizations and Linear Time Recognition of Helly Circular-Arc Graphs

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