## 8 Discussion  
Our experimental results show that both the tree compatibility testing algorithm of [10] and the IDPP algorithm of [9] performed at least as well as their theoretical worst-case bounds, and often better, if implemented using HDT(0), a much-simplified version of the HDT dynamic connectivity data structure.  
The results of Section 7 indicate that the main reason for the observed performance of HDT(0) is that the components that were scanned in search for replacement edges tended to be extremely small. Since we observed this phenomenon for a wide range of input profiles, we suspect that it is not an artifact of our experimental setup, but instead reflects a basic property of the graphs with which we are dealing. Indeed, BuildNT and PPSS use very special kinds of graphs--constructed from profiles of phylogenetic trees by gluing leaves with the same label--and perform deletions top-down. It is an open question whether there is a way to bound the total sizes of the smaller trees encountered during the execution of those algorithms, either asymptotically or in expectation.  
Profiles consisting of binary trees--and, in particular, triples--are quite common in practice. Proposition 2(1b) of Section 7 implies that for such profiles, certain spanning forests are better than others for maintaining connectivity information. A \"good\" spanning forest is one where the number of semi-universal nodes incident to only one tree edge is large, relative to the total number of semi-universal nodes. The results reported in Section 7.3 (in particular, Table 17) indicate that the spanning forests our programs generated were good in this sense, despite the fact that the programs took no special measures to ensure this. It is an open question whether there is an analytical explanation for this phenomenon. Another open question is whether good spanning forests always exist and, if so, whether they can be constructed and maintained efficiently.  
In our experiments, we never encountered a setting where HDT outperformed HDT(0). Of course, this does not mean that the latter is always to be preferred over the former. It would be interesting to find an application of dynamic graph connectivity where HDT is preferable to HDT(0) in practice.  
**Supplementary Materials:** Additional figures and tables are available online at [[http://www.mdpi.com/1999-4893/12/3/53/sl](http://www.mdpi.com/1999-4893/12/3/53/sl)]([http://www.mdpi.com/1999-4893/12/3/53/sl](http://www.mdpi.com/1999-4893/12/3/53/sl)). Figures S1-S17, Tables S1-S46.  
**Author Contributions:** Conceptualization, D.F.-B. and L.L.; methodology, D.F.-B. and L.L.; software, L.L.; validation, D.F.-B. and L.L.; formal analysis, D.F.-B. and L.L.; investigation, L.L.; writing, original draft preparation, D.F.-B. and L.L.; writing, review and editing, D.F.-B. and L.L.; visualization, L.L.; supervision, D.F.-B.; project administration, D.F.-B.; funding acquisition, D.F.-B.  
**Funding:** This research was funded by the National Science Foundation Grants IOS-1444806 and CCF-1422134.  
**Acknowledgments:** The authors thank the reviewers for their comments, which helped to improve the presentation of the paper.  
**Conflicts of Interest:** The authors declare no conflict of interest.