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:
- an enumeration formula, and an asymptotic of 23n −Θ(logn);
- an optimal data structure of asymptotically 3n bits, built in
O(n) time, supporting adjacency and degree queries in worst-case
constant time and neighbors query of a degree-d node in worst-case
O(d) time.
- an O(n) expected time uniform random generating algorithm.