14.1 Introduction

Given qimages and Rimages, a(R, q)polycycle P is a nonempty 2-connected map on a closed surface S with faces partitioned in two nonempty sets F1 and F2, so that:

(1) all elements of F1 (called proper faces) are combinatorial i-gons with iR;

(2) all elements of F2 (called holes) are pairwisely disjoint, that is, have no common vertices;

(3) all vertices have degree within {2,..., q} and all interior (i.e., not on the boundary of a hole) vertices are q-valent.

The map P can be finite or infinite and some of the faces of the set F2 can be i-gons with iR or have a countable number of edges. In practice almost all the maps occurring here will be plane graphs, which most often will be finite plane graphs. Note that while any finite plane graph has a unique exterior face, an infinite plane graph can have any number of exterior faces, including 0 and infinity. The exterior faces will always be holes.

An isomorphism between two maps, G1 and G2, is a function φ mapping vertices, edges, and faces of G1 to those of G2 and preserving inclusion relations. Two (R, q)-polycycles, P1 and P2, are isomorphic if there is an isomorphism φ of corresponding plane graphs that maps the set of holes of P1 to the set of holes of P2. The automorphism group Aut(G) of a map G is the group of all ...

Get Analysis of Complex Networks now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.