English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Thesis

Sampling Rooted 3-Connected Planar Graphs in Deterministic Polynomial Time

MPS-Authors
/persons/resource/persons44705

Johannsen,  Daniel
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available
Citation

Johannsen, D. (2006). Sampling Rooted 3-Connected Planar Graphs in Deterministic Polynomial Time. Master Thesis, Humboldt-Universität zu Berlin, Saarbrücken.


Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-23E5-0
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.