Matching and spanning in certain planar graphs

Call a connected planar graphG legal if it has at least two nodes, no parallel edges or self-loops and at most two terminals (degree 1 nodes) and all terminals and degree 2 nodes are exterior. This class of graphs arose in connection with a two-dimensional generating system for modeling growth by binary cell division. Showing that any permitted pattern can be generated properly requires a matching or pairing lemma. The vertex set of a legal graph withn nodes can be split intop adjacent pairs ands singletons withs p, resulting in a matching which includes at least (2left[ {frac{n}{3}} right]) nodes. This bound is sharp in the sense that there are legal graphs for which this matching is maximum. The matching can be implemented by a linear time algorithm. A legal graph witht terminals and n≥4 nodes has a spanning tree with at most (left[ {frac{{n - t}}{2}} right] + t) terminals; this bound is sharp. Such a spanning tree can be constructed by an algorithm which operates in almost linear time.