Font size: Αα Αα Αα hide gadgets
You are here: Theses » MSc » Vasiliki Velona

MSc thesis of Vasiliki Velona

Asymptotic analysis of outerplanar graphs with subgraph obstructions

Supervisors: Juanjo Rué Perna, Dimitrios M. Thilikos

In this thesis we study techniques for combinatorial specification and asymptotic enumeration in the context of analytic combinatorics. Our guide through this variety of techniques is the enumeration of certain types of planar graphs, under subgraph exclusion constraints. In particular, we examine outerplanar graphs where the constraint is the exclusion of cycles of certain length. We build specifications for the 2-connected components that exclude certain cycles in order to obtain asymptotics for the general constrainded outerplanar class. The challenges here are combinatorial as well as computational, as the specifications become more involved when the length of the excluded cycle grows and the generating functions obtained are in implicit form. The combinatorial language that we use is the so-called Symbolic Method that comes in hand with corresponding analytic techniques. Furthermore, we study certain parameters of general outerplanar graphs, namely the number of triangles and quadrangles. We obtain Gaussian limiting distibutions and extract explicit constants for the mean and variance.

Defended: June 24, 2016.

Scientific committee


Download thesis.


Web standards: XHTML1.0, CSS3.
© 1996 – 2018 MPLA: Graduate program in Logic, Algorithms and Computation.
Contact the webmaster.