Matching and spanning in certain planar graphs |
| |
Authors: | J. W. Carlyle S. A. Greibach A. Paz |
| |
Affiliation: | 1. Department of Computer Science, University of California, California, Los Angeles, USA 2. Department of Computer Science, Technion-Israel Institute of Technology, Haifa, Israel
|
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|