Recently planar structures, such as planar graphs and outerplanar graphs, have received much attention.
Typical questions one would ask about them are the following:
For the asymptotic enumeration we interpret the decomposition in terms of generating funtions and derive the asymptotic number, using singularity analysis. For the exact enumeration and the uniform generation we use the so-called recursive method: We derive recursive counting formulas along the decomposition, which yields a deterministic polynomial time algorithm to sample a planar structure that is uniformly distributed.
We apply these methods to several labeled planar structures, e.g., planar graphs, cubic planar graphs, series-parallel graphs, and outerplanar graphs.
- How many of them are there (exactly or asymptotically)?
- Can we sample a random instance uniformly at random?
- What properties does a random planar structure have ?
For the asymptotic enumeration we interpret the decomposition in terms of generating funtions and derive the asymptotic number, using singularity analysis. For the exact enumeration and the uniform generation we use the so-called recursive method: We derive recursive counting formulas along the decomposition, which yields a deterministic polynomial time algorithm to sample a planar structure that is uniformly distributed.
We apply these methods to several labeled planar structures, e.g., planar graphs, cubic planar graphs, series-parallel graphs, and outerplanar graphs.
Planar graphs
- Generating labeled planar graphs uniformly at random
- Sampling unlabeled biconnected planar graphs
- A direct decomposition of 3-connected planar graphs
- A complete grammar for decomposing a family of graphs into 3-connected components
- The enumeration of planar graphs via Wick's theorem
Cubic planar graphs
- Random cubic planar graphs : asymptotic number of labeled cubic planar graphs and typical properties of random cubic planar graphs
- Decomposing, counting, and generating unlabeled cubic planar graphs uniformly at random
Outerplanar graphs
- Generating outerplanar graphs uniformly at random : recursive counting and uniform sampling of labeled and unlabeled outerplanar graphs
- The asymptotic number of labeled series-parallel and outerplanar graphs
- Asymptotic number of unlabeled outerplanar graphs
Cycle-pointing for unlabeled structures
Other related works
- On the logical complexity of convex polygon dissections
- Random outerplanar graphs, Studienarbeit by Stefan Vigerske
- Asymptotic enumeration of unlabeled outerplanar graphs, Diplomarbeit by Stefan Vigerske
- Counting and uniform generation of labeled planar structures, Diplomarbeit by Mike Löffler
- Planar structures, Research focus of the research group "Algorithms and Complexity"
