Counting hexagonal patches and independent sets in circle graphs

DOI10.1007/s00453-011-9561-yzbMath1239.05093MaRDI QIDQ2429365

Paul Bonsma, Felix Breuer

Publication date: 26 April 2012

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-011-9561-y

zbMATH Keywords

planar graph; counting problem; fullerene; circle graph; polyhex; fusene; hexagonal patch

Mathematics Subject Classification ID

05C90: Applications of graph theory

05C30: Enumeration in graph theory

05C10: Planar graphs; geometric and topological aspects of graph theory

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

A Faster Algorithm for Maximum Induced Matchings on Circle Graphs, A Maximum Weight Clique Algorithm For Dense Circle Graphs With Many Shared Endpoints

Cites Work

• Filling of a given boundary by \(p\)-gons and related problems
• Numbers of faces in disordered patches
• Reducing prime graphs and recognizing circle graphs
• Detecting and decomposing self-overlapping curves
• The nature and meaning of perturbations in geometric computing
• Pentagon-hexagon-patches with short boundaries
• Boundary uniqueness of fusenes
• Finding Fullerene Patches in Polynomial Time
• Graph Classes: A Survey
• Recognition of Circle Graphs
• Recognizing circle graphs in polynomial time
• Algorithms and Computation
• Efficiently implementing maximum independent set algorithms on circle graphs
• Algorithms for a maximum clique and a maximum independent set of a circle graph
• A constructive enumeration of nanotube caps
• Extensions to the disk of properly nested plane immersions of the circle
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item