Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
DOI: 10.7155/jgaa.00105 Canonical Decomposition of Outerplanar Maps and Application to Enumeration, Coding and Generation Nicolas Bonichon , Cyril Gavoille , and Nicolas Hanusse Vol. 9, no. 2, pp. 185-204, 2005. Regular paper Abstract In this article we define a canonical decomposition of rooted outerplanar maps into a spanning tree and a list of edges. This decomposition, constructible in linear time in the Word-RAM model, implies the existence of bijection between rooted outerplanar maps with n nodes and bicolored rooted ordered trees with n nodes where all the nodes of the last branch are colored white. As a consequence, for rooted outerplanar maps of n nodes, we derive:
|
Submitted: July 2003. Revised: August 2005. Communicated by Xin He |
Journal of Graph Algorithms and Applications |