Minimal Cycle Bases of Outerplanar Graphs

Josef Leydold and Peter F. Stadler


2-connected outerplanar graphs have a unique minimal cycle basis with length 2|E|-|V|. They are the only Hamiltonian graphs with a cycle basis of this length.

Mathematics Subject Classification: 05C38 (paths and cycles), 92D20 (protein sequences, DNA sequences)

Keywords: Minimal Cycle Basis, Outerplanar Graphs

Download Paper   PostScript | PDF      [EJC]