Counting hexagonal patches and independent sets in circle graphs
From MaRDI portal
Publication:2429365
DOI10.1007/s00453-011-9561-yzbMath1239.05093MaRDI QIDQ2429365
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
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