Secondary structures of polynucleotides can be view as a certain class of planar vertex-labeled graphs. We construct recursion formulae enumerating various sub-classes of these graphs as well as certain structural elements (sub-graphs). First order asymptotics are derived and their dependence on the logic of base pairing is computed and discussed.