Family Trees for Enumeration.

In this paper we design efficient algorithms for enumerating (1) the rooted trees with exactly n vertices, (2) the maximal planar graphs with exactly n vertices and (3) the linear extensions of a given poset. Those algorithms are based on tree structures of objects, called the family trees. The first algorithm enumerates each ordered tree with exactly n vertices in O (1) time for each after O (n) time preprocessing. The second algorithm enumerates each maximal planar graph with exactly n vertices in O (n 3) time for each on average. The third algorithm enumerates each linear extension of a given poset in O (1) time for each after O (n 2) time preprocessing, where n is the number of the element in the set of the poset. [ABSTRACT FROM AUTHOR]