Counting hexagonal patches and independent sets in circle graphs

DOI10.1007/s00453-011-9561-yzbMath1239.05093OpenAlexW2064729717MaRDI 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 graphcounting problemfullerenecircle graphpolyhexfusenehexagonal patch

Mathematics Subject Classification ID

Applications of graph theory (05C90) Enumeration in graph theory (05C30) Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

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

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: Counting hexagonal patches and independent sets in circle graphs