Document Open Access Logo

Counting Planar Tanglegrams

Authors Dimbinaina Ralaivaosaona, Jean Bernoulli Ravelomanana, Stephan Wagner

PDF
Thumbnail PDF

File

LIPIcs.AofA.2018.32.pdf
  • Filesize: 477 kB
  • 18 pages

Document Identifiers

Author Details

Dimbinaina Ralaivaosaona
  • Department of Mathematical Sciences, Stellenbosch University, Stellenbosch, South Africa
Jean Bernoulli Ravelomanana
  • Department of Mathematical Sciences, Stellenbosch University, Stellenbosch, South Africa
Stephan Wagner
  • Department of Mathematical Sciences, Stellenbosch University, Stellenbosch, South Africa

Funding

  • Wagner, Stephan: The third author is supported by the National Research Foundation of South Africa under grant number 96236.

Cite As Get BibTex

Dimbinaina Ralaivaosaona, Jean Bernoulli Ravelomanana, and Stephan Wagner. Counting Planar Tanglegrams. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 32:1-32:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.AofA.2018.32

Abstract

Tanglegrams are structures consisting of two binary rooted trees with the same number of leaves and a perfect matching between the leaves of the two trees. We say that a tanglegram is planar if it can be drawn in the plane without crossings. Using a blend of combinatorial and analytic techniques, we determine an asymptotic formula for the number of planar tanglegrams with n leaves on each side.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Enumeration
  • Mathematics of computing → Generating functions
Keywords
  • rooted binary trees
  • tanglegram
  • planar
  • generating functions
  • asymptotic enumeration
  • singularity analysis

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Sara C. Billey, Matjaž Konvalinka, and Frederick A. Matsen. On the enumeration of tanglegrams and tangled chains. J. Combin. Theory Ser. A, 146:239-263, 2017. Google Scholar
  2. Kevin Buchin, Maike Buchin, Jaroslaw Byrka, Martin Nöllenburg, Yoshio Okamoto, Rodrigo I. Silveira, and Alexander Wolff. Drawing (complete) binary tanglegrams: hardness, approximation, fixed-parameter tractability. Algorithmica, 62(1-2):309-332, 2012. Google Scholar
  3. Éva Czabarka, László Székely, and Stephan Wagner. A tanglegram Kuratowski theorem. Preprint, submitted; URL: https://arxiv.org/abs/1708.00309.
  4. NIST Digital Library of Mathematical Functions. http://dlmf.nist.gov/, Release 1.0.15 of 2017-06-01. F. W. J. Olver, A. B. Olde Daalhuis, D. W. Lozier, B. I. Schneider, R. F. Boisvert, C. W. Clark, B. R. Miller and B. V. Saunders, eds.
  5. Henning Fernau, Michael Kaufmann, and Mathias Poths. Comparing trees via crossing minimization. In Proceedings of the 25th International Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS '05, pages 457-469, Berlin, Heidelberg, 2005. Springer-Verlag. Google Scholar
  6. Philippe Flajolet and Robert Sedgewick. Analytic combinatorics. Cambridge University press, 2009. Google Scholar
  7. Frank Harary and Edgar M. Palmer. Graphical Enumeration. Academic Press, 1973. Google Scholar
  8. Danièle Huguet and Dov Tamari. La structure polyédrale des complexes de parenthésages. J. Combin. Inform. System Sci., 3(2):69-81, 1978. Google Scholar
  9. Matjaž Konvalinka and Stephan Wagner. The shape of random tanglegrams. Adv. in Appl. Math., 78:76-93, 2016. Google Scholar
  10. Frederick A. Matsen IV, Sara C. Billey, Arnold Kas, and Matjaž Konvalinka. Tanglegrams: a reduction tool for mathematical phylogenetics. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 15(1):343-349, 2018. Google Scholar
  11. N.J.A. Sloane, editor. The On-line Encyclopedia of Integer sequences. Published electronically at https://oeis.org, 2018. Google Scholar
  12. Roderic D. M. Page. Tangled trees: phylogeny, cospeciation, and coevolution. University of Chicago Press, 2003. Google Scholar
  13. Hassler Whitney. Non-separable and planar graphs. Trans. Amer. Math. Soc., 34(2):339-362, 1932. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact