Enumeration of tanglegrams
Date
2018-03
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
ENGLISH ABSTRACT : Tanglegrams are graphs obtained by taking two binary rooted trees with the same number
of leaves and a perfect matching between the leaves of the two trees. Tanglegrams appear in
biology in the study of cospeciation or coevolution, and in computer science in the study of
software projects and clustering problems. This thesis is concerned with the enumeration of
tanglegrams: we first prove an exact formula for the number of non-isomorphic tanglegrams
on n leaves and an asymptotic formula for the same quantity as n tends to infinity. Next,
we study several parameters of random tanglegrams such as the number of occurrences of
subtrees or the distribution of root branches. Finally, our main contribution in this thesis
is on the enumeration of planar tanglegrams on n leaves, where a planar tanglegram is a
tanglegram that can be drawn in the plane without crossings.
AFRIKAANSE OPSOMMING : Tanglegramme is grafieke wat uit twee binêre wortelbome met dieselfde aantal blare en ’n perfekte matching tussen die blare van die twee bome bestaan. Tanglegramme verskyn in biologie in die studie van kospesiasie en koëvolusie, en in rekenaarwetenskap in die ondersoek van sagtewareprojekte en groeperingsprobleme. Hierdie proefskrif behandel die aftelling van tanglegramme: ons bewys eers ’n formule vir die aantal van nie-isomorfe tanglegramme met n blare en ’n asimptotiese formule vir hierdie aantal as n na oneindig strewe. Verder bestudeer on ’n verskeidenheid van parameters van lukrake tanglegramme soos die aantal voorkoms van deelbome of die verdeling van worteltakke. Laastens is ons hoofbydrag in hierdie proefskrif die aftelling van planêre tanglegramme met n blare, waar ’n planêre tanglegram ’n tanglegram is wat in die vlak sonder kruisings geteken kan word.
AFRIKAANSE OPSOMMING : Tanglegramme is grafieke wat uit twee binêre wortelbome met dieselfde aantal blare en ’n perfekte matching tussen die blare van die twee bome bestaan. Tanglegramme verskyn in biologie in die studie van kospesiasie en koëvolusie, en in rekenaarwetenskap in die ondersoek van sagtewareprojekte en groeperingsprobleme. Hierdie proefskrif behandel die aftelling van tanglegramme: ons bewys eers ’n formule vir die aantal van nie-isomorfe tanglegramme met n blare en ’n asimptotiese formule vir hierdie aantal as n na oneindig strewe. Verder bestudeer on ’n verskeidenheid van parameters van lukrake tanglegramme soos die aantal voorkoms van deelbome of die verdeling van worteltakke. Laastens is ons hoofbydrag in hierdie proefskrif die aftelling van planêre tanglegramme met n blare, waar ’n planêre tanglegram ’n tanglegram is wat in die vlak sonder kruisings geteken kan word.
Description
Thesis (MSc)--Stellenbosch University, 2018.
Keywords
Generating function, UCTD, Tanglegrams (Mathematics), Triangulation (Mathematics), Binary trees, Matching leaves (Mathematics), Tangled chain (Mathematics)