MSc thesis of Βασιλικής Βελώνας
Asymptotic analysis of outerplanar graphs with subgraph obstructions
Supervisors: Juanjo Rué Perna, Δημήτριος Μ. Θηλυκός
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: 24 Ιουνίου 2016.