A planar graph is a graph that can be drawn
in the plane, with points for the nodes and lines for the edges, such that
the lines cross only in the points for the nodes. Planarity is one
of the most prominent graph properties, and frequently occurs in
theory and practice. However, not much is known about about
random planar graphs. If we consider planar
graphs up to isomorphism (in this case we speak of unlabeled random planar graphs) even less is known.
Staff
- Professor: Prof. Dr. Hans Jürgen Prömel
- Researchers: Dr. Manuel Bodirsky, Dr. Mihyun Kang
- Students: Daniel Johannsen, Dirk Schlatter, Stefan Vigerske
- Alumni: Prof. Dr. Anusch Taraz, Dr. Clemens Gröpl, Dr. Deryk Osthus, Mike Löffler
Topics
- Random structures in the plane and their properties
- Enumeration of planar structures
- Generating functions and asymptotic analysis
- Efficient sampling of random planar structures
Results
- Labeled planar graphs: Random planar graphs; Exact enumeration and random sampling
- Cubic planar graphs: Random labeled cubic planar graphs ; Sampling of random unlabeled cubic planar graphs
- Series-parallel and outerplanar graphs: The asymptotic number of labeled series-parallel and outerplanar graphs; Asymptotic number of unlabeled outerplanar graphs; Exact enumeration and random sampling of labeled and unlabeled outerplanar graphs; Typical properties of random outerplanar graphs
- Two-connected planar graphs: Random sampling of unlabeled two-connected planar graphs
- Three-connected planar graphs: Asymptotic number and random sampling
- Existence and structure of planar subgraphs
- The planar graph process
Implementations and Data
- Labeled planar graphs: Enumeration
- Labeled outerplanar Graphs: Sampling; Enumeration
- Unlabeled outerplanar Graphs: Enumeration
- Labeled cubic planar graphs: Sampling; Enumeration
Related projects in Berlin
- Research group Algorithms, Structure, Randomness
- Research focus discrete structures
- Research forcu approximation algorithms, randomized algorithms, and probabilistic analysis
- Graduate program Combinatorics, Geometry, and Computation
Useful links
- The On-Line Encyclopedia of Integer Sequences, by Neil J. A. Sloane: http://www.research.att.com/~njas/sequences/
- A book on singularity analysis by P. Flajolet and R. Sedgewick: http://algo.inria.fr/flajolet/Publications/AnaCombi1to9.pdf
- Mathematical constants, by Steven R. Finch: http://pauillac.inria.fr/algo/bsolve/
- A collection of algorithms for listing combinatorical structures, by Gunnar Brinkmann and Brendan McKay: http://cs.anu.edu.au/~bdm/plantri/
Deutsch