MPI-INF Logo
Publications

Thesis (Server    domino.mpi-inf.mpg.de)

Thesis

Master's thesis | @MastersThesis{Johannsen2006a, ... | Masterarbeit

Johannsen, Daniel

Sampling Rooted 3-Connected Planar Graphs in Deterministic Polynomial Time

Humboldt-Universität zu Berlin, April, 2006

In this thesis an algorithm for sampling rooted 3-connected planar graphs (c-nets) in deterministic polynomial time is presented. The algorithm is based on a decomposition strategy for c-nets, which is formulated as a system of bijections between classes of c-nets parameterized by the number of vertices, faces, and edges on the outer face. This system is then used in three ways: First, as system of recursive equations to derive the sizes of above classes by using an algorithm based on dynamic programming. Second, as system of equations of generating functions to derive an algebraic generating function and a single parameter recursion formula for c-nets. Third, as composition scheme to sample c-nets uniformly at random with the recursive method of sampling. The thesis is based on the paper \emph{A Direct Decomposition of 3-connected Planar Graphs} by Manuel Bodirsky, Clemens Gr{\"o}pl, Mihyun Kang and the author~\cite{3connplanar} and extends it by the parameter for the number of edges and a full proof of the decomposition.

random planar graphs sampling enumeration
Public
Manuel Bodirsky
Amin Coja-Oghlan
Manuel Bodirsky
Completed
1
March
2007
Max-Planck-Institut für Informatik
Algorithms and Complexity Group
experts only
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort


BibTeX Entry:
@MASTERSTHESIS{Johannsen2006a,
AUTHOR = {Johannsen, Daniel},
TITLE = {Sampling Rooted 3-Connected Planar Graphs in Deterministic Polynomial Time},
SCHOOL = {Humboldt-Universit{\"a}t zu Berlin},
YEAR = {2006},
TYPE = {Master's thesis}
MONTH = {April},
}





Entry last modified by Daniel Johannsen, 02/16/2009
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Daniel Johannsen
Created
03/08/2007 05:26:50 PM
Revisions
7.
6.
5.
4.
3.
Editor(s)
Daniel Johannsen
Daniel Johannsen
Daniel Johannsen
Daniel Johannsen
Daniel Johannsen
Edit Dates
02/16/2009 01:30:33 AM
02/16/2009 01:27:33 AM
02/15/2009 08:31:08 PM
29.04.2008 12:46:49
08.03.2007 17:28:31