Counting Hexagonal Patches and Independent Sets in Circle Graphs

被引：0
作者：
Paul Bonsma
Felix Breuer
机构：
[1] Technische Universität Berlin,Institut für Mathematik
[2] Freie Universität Berlin,Institut für Mathematik
来源：
Algorithmica | 2012年 / 63卷
关键词：
Counting problem; Planar graph; Circle graph; Fullerene; Hexagonal patch; Fusene; Polyhex;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
A hexagonal patch is a plane graph in which inner faces have length 6, inner vertices have degree 3, and boundary vertices have degree 2 or 3. We consider the following counting problem: given a sequence of twos and threes, how many hexagonal patches exist with this degree sequence along the outer face? This problem is motivated by the enumeration of benzenoid hydrocarbons and fullerenes in computational chemistry. We give the first polynomial time algorithm for this problem. We show that it can be reduced to counting maximum independent sets in circle graphs, and give a simple and fast algorithm for this problem. It is also shown how to subsequently generate hexagonal patches.
引用
收藏
页码：645 / 671
页数：26
相关论文
共 39 条
  • [1] Bornhöft J.(2003)Pentagon–hexagon-patches with short boundaries Eur. J. Comb. 24 517-529
  • [2] Brinkmann G.(1987)Reducing prime graphs and recognizing circle graphs Combinatorica 7 243-254
  • [3] Greinus J.(2009)An efficient algorithm for the generation of planar polycyclic hydrocarbons with a given boundary MATCH Commun. Math. Comput. Chem. 62 209-220
  • [4] Bouchet A.(1997)A constructive enumeration of fullerenes J. Algorithms 23 345-358
  • [5] Brinkmann G.(2002)A constructive enumeration of nanotube caps Discrete Appl. Math. 116 55-71
  • [6] Coppens B.(2009)Numbers of faces in disordered patches J. Math. Chem. 45 263-278
  • [7] Brinkmann G.(2001)Allowed boundary sequences for fused polycyclic patches and related algorithmic problems J. Chem. Inf. Comput. Sci. 41 300-308
  • [8] Dress A.W.M.(2008)Filling of a given boundary by Discrete Appl. Math. 156 1518-1535
  • [9] Brinkmann G.(1992)-gons and related problems J. Phys. Chem. 96 6941-6944
  • [10] v. Nathusius U.(1970)Formation of carbon nanofibers Mich. Math. J. 17 377-383
1234