  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 study 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.
