Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00105
Canonical Decomposition of Outerplanar Maps and Application to Enumeration, Coding and Generation
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:
|
Journal Supporters
|