%0 Journal Article
%T Finding Fullerene Patches in Polynomial Time
%A Paul Bonsma
%A Felix Breuer
%J Computer Science
%D 2009
%I arXiv
%X We consider the following question, motivated by the enumeration of fullerenes. A fullerene patch is a 2-connected plane graph G in which inner faces have length 5 or 6, non-boundary vertices have degree 3, and boundary vertices have degree 2 or 3. The degree sequence along the boundary is called the boundary code of G. We show that the question whether a given sequence S is a boundary code of some fullerene patch can be answered in polynomial time when such patches have at most five 5-faces. We conjecture that our algorithm gives the correct answer for any number of 5-faces, and sketch how to extend the algorithm to the problem of counting the number of different patches with a given boundary code.
%U http://arxiv.org/abs/0907.2627v1