Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF D1 Publications :: Thesis :: Johannsen, Daniel

MPI-INF D1 Publications
Show all entries of:this year (2020)last year (2019)two years ago (2018)Open in Notes
Action:login to update

Thesis - Master's thesis | @MastersThesis | Masterarbeit

Author(s)*:Johannsen, Daniel
BibTeX citekey*:Johannsen2006a

Title, School
Title*:Sampling Rooted 3-Connected Planar Graphs in Deterministic Polynomial Time
School:Humboldt-Universität zu Berlin
Type of Thesis*:Master's thesis

Note, Abstract, Copyright
LaTeX Abstract: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.
Keywords:random planar graphs sampling enumeration
Download Access Level:Public
Download File(s):View attachments here:

Referees, Status, Dates
1. Referee:Manuel Bodirsky
2. Referee:Amin Coja-Oghlan
Supervisor:Manuel Bodirsky
Date Kolloquium:1 March 2007

MPG Unit:Max-Planck-Institut für Informatik
MPG Subunit:Algorithms and Complexity Group
Audience:experts only
Appearance:MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

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)

Daniel Johannsen
03/08/2007 05:26:50 PM
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