Canonical Decomposition of Outerplanar Maps and Application to Enumeration, Coding and Generation - Bonichon, Nicolas; Gavoille, Cyril; Hanusse, Nicolas (Journal of Graph Algorithms and Applications, 2005)
In this article we define a canonical decomposition of rootedouterplanar maps into a spanning tree and a list of edges. Thisdecomposition, constructible in linear time in the Word-RAM model, implies the existence ofbijection between rooted outerplanar maps with n nodes and bicoloredrooted ordered trees with n nodes where all the nodes of the lastbranch are colored white. As a consequence, for rooted outerplanarmaps of n nodes, we derive: <!----> an enumeration formula, and an asymptotic of 23n −Θ(logn); <!----> an optimal data structure of asymptotically 3n bits, built inO(n) time, supporting adjacency and degree queries in worst-case <!----> constant time and neighbors query of a degree-d node in worst-caseO(d) time. <!----> an O(n) expected time uniform random generating algorithm. <!----> <!---->