×

When can splits be drawn in the plane? (English) Zbl 1362.92049

Summary: Split networks are a popular tool for the analysis and visualization of complex evolutionary histories. Every collection of splits (bipartitions) of a finite set can be represented by a split network. Here we characterize which collection of splits can be represented using a planar split network. Our main theorem links these collections of splits with oriented matroids and arrangements of lines separating points in the plane. As a consequence of our main theorem, we establish a particularly simple characterization of maximal collections of these splits.

MSC:

92D15 Problems related to evolution
52C30 Planar arrangements of lines and pseudolines (aspects of discrete geometry)
05C90 Applications of graph theory
52C40 Oriented matroids in discrete geometry

Software:

FlatNJ; QNet
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] M. Balvočiūtė, A. Spillner, and V. Moulton, {\it FlatNJ: A novel network-based approach to visualize evolutionary and biogeographical relationships}, Syst. Biol., 63 (2014), pp. 383-396.
[2] A. Björner, M. Las Vergnas, B. Sturmfels, N. White, and G. M. Ziegler, {\it Oriented Matroids}, Cambridge University Press, New York, 1999. · Zbl 0944.52006
[3] J. Bohne, {\it Eine kombinatorische Analyse zonotopaler Raumaufteilungen}, Ph.D. thesis, Bielefeld University, Bielefeld, Germany, 1992. · Zbl 0836.52008
[4] D. Bryant and A. Dress, {\it Linearly independent split systems}, European J. Combin., 28 (2007), pp. 1814-1831. · Zbl 1121.93015
[5] D. Bryant and V. Moulton, {\it Neighbor-net: An agglomerative method for the construction of phylogenetic networks}, Mol. Biol. Evol., 21 (2004), pp. 255-265.
[6] P. Buneman, {\it The recovery of trees from measures of dissimilarity}, in Mathematics in the Archaeological and Historical Sciences, D. G. Kendall, F. R. Hodson, and P. Tautu, ed., Edinburgh University Press, Edinburgh, 1971, pp. 387-395.
[7] D. v. Djoković, {\it Distance-preserving subgraphs of hypercubes}, J. Combin. Theory Ser. B, 14 (1973), pp. 263-267. · Zbl 0245.05113
[8] A. Dress and D. Huson, {\it Constructing splits graphs}, IEEE/ACM Trans. Comput. Biol. Bioinform., 1 (2004), pp. 109-115.
[9] D. Eppstein, {\it Algorithms for drawing media}, in Graph Drawing, J. Pach, ed., Lecture Notes in Comput. Sci. 3383, Springer, Berlin, 2005, pp. 173-183. · Zbl 1111.68576
[10] D. Eppstein, J.-C. Falmagne, and S. Ovchinnikov, {\it Media Theory}, Springer, Berlin, 2008. · Zbl 1149.00010
[11] S. Felsner, {\it Geometric Graphs and Arrangements}, Vieweg, Wiesbaden, Germany, 2004. · Zbl 1051.05036
[12] S. Felsner and H. Weil, {\it Sweeps, arrangements and signotopes}, Discrete Appl. Math., 109 (2001), pp. 67-94. · Zbl 0967.68159
[13] J. Folkman and J. Lawrence, {\it Oriented matroids}, J. Combin. Theory Ser. B, 25 (1978), pp. 199-236. · Zbl 0325.05019
[14] B. Gärtner and E. Welzl, {\it Vapnik-Chervonenkis dimension and (pseudo-)hyperplane arrangements}, Discrete Comput. Geom. 12 (1994), pp. 399-432. · Zbl 0813.52013
[15] J. E. Goodman and R. Pollack, {\it On the combinatorial classification of nondegenerate configurations in the plane}, J. Combin. Theory Ser. A, 29 (1980), pp. 220-235. · Zbl 0448.05016
[16] J. E. Goodman and R. Pollack, {\it A theorem of ordered duality}, Geom. Dedicata, 12 (1982), pp. 63-74. · Zbl 0494.51002
[17] S. Grünewald, K. Forslund, A. Dress, and V. Moulton, {\it QNet: An agglomerative method for the construction of phylogenetic networks from weighted quartets}, Mol. Biol. Evol., 24 (2007), pp. 532-538.
[18] K. Handa, {\it A characterization of oriented matroids in terms of topes}, European J. Combin., 11 (1990), pp. 41-45. · Zbl 0748.05042
[19] T. Hastie, R. Tibshirani, and J. Friedman, {\it The Elements of Statistical Learning}, 2nd ed., Springer, New York, 2009. · Zbl 1273.62005
[20] D. Huson and D. Bryant, {\it Application of phylogenetic networks in evolutionary studies}, Mol. Biol. Evol., 23 (2006), pp. 254-267.
[21] D. Huson, R. Rupp, and C. Scornavacca, {\it Phylogenetic Networks}, Cambridge University Press, New York, 2010.
[22] M. Las Vergnas, {\it Matroïdes Orientables}, C. R. Acad. Sci. Paris, 280 (1975), pp. 61-64. · Zbl 0304.05013
[23] F. Levi, {\it Die Teilung der projektiven Ebene durch Gerade oder Pseudogerade}, Ber. Math.-Phys. Kl. Sächs. Akad. Wiss. Leipzig, 78 (1926), pp. 256-267. · JFM 52.0575.01
[24] J. Richter-Gebert and G. M. Ziegler, {\it Zonotopal tilings and the Bohne-Dress Theorem}, in Jerusalem Combinatorics, AMS, Providence, RI, 1994, pp. 211-232. · Zbl 0842.05018
[25] C. Semple and M. Steel, {\it Phylogenetics}, Oxford University Press, Oxford, 2003. · Zbl 1043.92026
[26] P. Shor, {\it Stretchability of pseudoline arrangements is NP-hard}, in Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift, American Math. Soc., Providence, RI, 1991, pp. 531-554.
[27] A. Spillner, B. Nguyen, and V. Moulton, {\it Constructing and drawing regular planar split networks}, IEEE/ACM Trans. Comput. Biol. Bioinform., 9 (2012), pp. 395-407.
[28] R. Wetzel, {\it Zur Visualisierung abstrakter Ähnlichkeitsbeziehungen}, Ph.D. thesis, Bielefeld University, Bielefeld, Germany, 1995. · Zbl 0847.05094
[29] T. Zaslavsky, {\it Facing up to arrangements: Face-count formulas for partitions of space by hyperplanes}, Mem. Amer. Math. Soc., 1 (1975), pp. 1-102. · Zbl 0296.50010
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.