It is known that any n-point set in the d-dimensional Euclidean space ℝ^d, for d = O(1), admits: 1) A (1+ε)-spanner with maximum degree Õ(ε^{-d+1}) and with lightness Õ(ε^{-d}), for any ε > 0. 2) A (1+ε)-tree cover with Õ(n ⋅ ε^{-d+1}) trees and maximum degree of O(1) in each tree. Moreover, all the parameters in these constructions are optimal: For any 2 ≤ d = O(1), there exists an n-point set in ℝ^d, for which any (1+ε)-spanner has Ω̃(n⋅ε^{-d+1}) edges and lightness Ω̃(ε^{-d}). The upper bounds for Euclidean spanners rely heavily on the spatial property of cone partitioning in ℝ^d, which does not seem to extend to the wider family of doubling metrics, i.e., metric spaces of constant doubling dimension. In doubling metrics, a simple spanner construction from two decades ago, the net-tree spanner, has Õ(n⋅ε^{-d}) edges, and it could be transformed into a spanner of maximum degree Õ(ε^{-d}) and lightness Õ(n⋅ε^{-(d+1)}) by pruning redundant edges. Moreover, a careful refinement of the net-tree spanner yields a (1+ε)-tree cover with Õ(ε^{-d}) trees. Despite a large body of work, the problem of obtaining tight bounds for spanners and tree covers in the wider family of doubling metrics has remained elusive. We resolve this problem by presenting: 1) A surprisingly simple and tight lower bound, which shows that the net-tree spanner and its pruned version are optimal with respect to all the involved parameters. 2) A new construction of (1+ε)-tree covers with Õ(n⋅ε^{-d}) trees, with maximum degree O(1) in each tree. This construction is optimal with respect to the number of trees and maximum degree.

Sparse shortcuttings of trees - equivalently, sparse 1-spanners for tree metrics with bounded hop-diameter - have been studied extensively (under different names and settings), since the pioneering works of [Andrew Chi-Chih Yao, 1982; Chazelle, 1987; Noga Alon and Baruch Schieber, 1987; Hans L. Bodlaender et al., 1994], initially motivated by applications to range queries, online tree product, and MST verification, to name a few. These constructions were also lifted from trees to other graph families using known low-distortion embedding results. The works of [Andrew Chi-Chih Yao, 1982; Chazelle, 1987; Noga Alon and Baruch Schieber, 1987; Hans L. Bodlaender et al., 1994] establish a tight tradeoff between hop-diameter and sparsity (or average degree) for tree shortcuttings and imply constant-hop shortcuttings for n-node trees with sparsity O(log^* n). Despite their small sparsity, all known constant-hop shortcuttings contain dense subgraphs (of sparsity Ω(log n)), which is a significant drawback for many applications. We initiate a systematic study of constant-hop tree shortcuttings that are "tree-like". We focus on two well-studied graph parameters that measure how far a graph is from a tree: arboricity and treewidth. Our contribution is twofold. - New upper and lower bounds for tree-like shortcuttings of trees, including an optimal tradeoff between hop-diameter and treewidth for all hop-diameter up to O(log log n). We also provide a lower bound for larger values of k, which together yield hop-diameter× treewidth = Ω((log log n)²) for all values of hop-diameter, resolving an open question of [Arnold Filtser and Hung Le, 2022; H. Le, 2023]. - Applications of these bounds, focusing on low-dimensional Euclidean and doubling metrics. A seminal work of Arya et al. [S. Arya et al., 1995] presented a (1+ε)-spanner with constant hop-diameter and sparsity O(log^* n), but with large arboricity. We show that constant hop-diameter is sufficient to achieve arboricity O(log^*{n}). Furthermore, we present a (1+ε)-stretch routing scheme in the fixed-port model with 3 hops and a local memory of O(log²n / log log n) bits, resolving an open question of [Omri Kahalon et al., 2022].

For a weighted graph $G = (V, E, w)$ and a designated source vertex $s \in V$, a spanning tree that simultaneously approximates a shortest-path tree w.r.t. source $s$ and a minimum spanning tree is called a shallow-light tree (SLT). Specifically, an $(α, β)$-SLT of $G$ w.r.t. $s \in V$ is a spanning tree of $G$ with root-stretch $α$ (preserving all distances between $s$ and the other vertices up to a factor of $α$) and lightness $β$ (its weight is at most $β$ times the weight of a minimum spanning tree of $G$). Despite the large body of work on SLTs, the basic question of whether a better approximation algorithm exists was left untouched to date, and this holds in any graph family. This paper makes a first nontrivial step towards this question by presenting two bicriteria approximation algorithms. For any $ε>0$, a set $P$ of $n$ points in constant-dimensional Euclidean space and a source $s\in P$, our first (respectively, second) algorithm returns, in $O(n \log n \cdot {\rm polylog}(1/ε))$ time, a non-Steiner (resp., Steiner) tree with root-stretch $1+O(ε\log ε^{-1})$ and weight at most $O(\mathrm{opt}_ε\cdot \log^2 ε^{-1})$ (resp., $O(\mathrm{opt}_ε\cdot \log ε^{-1})$), where $\mathrm{opt}_ε$ denotes the minimum weight of a non-Steiner (resp., Steiner) tree with root-stretch $1+ε$.

In their seminal paper, Althöfer et al. (DCG 1993) introduced the greedy spanner and showed that, for any weighted planar graph \(G\), the weight of the greedy \((1+\epsilon)\)-spanner is at most \((1+\tfrac{2}{\epsilon})\cdot \textrm w(\mathsf{MST}(G))\), where \(\textrm w(\mathsf{MST}(G))\) is the weight of a minimum spanning tree \(\mathrm{MST}(G)\) of \(G\). This bound is optimal in an \(\textcolor{#ff6666}{existential\ sense}\): there exist planar graphs \(G\) for which any \((1+\epsilon)\)-spanner has a weight of at least \((1+\tfrac{2}{\epsilon})\cdot w(\mathrm{MST}(G))\).

A $(1+\varepsilon)\textit{-stretch tree cover}$ of a metric space is a collection of trees, where every pair of points has a $(1+\varepsilon)$-stretch path in one of the trees. The celebrated $\textit{Dumbbell Theorem}$ [Arya et~al. STOC'95] states that any set of $n$ points in $d$-dimensional Euclidean space admits a $(1+\varepsilon)$-stretch tree cover with $O_d(\varepsilon^{-d} \cdot \log(1/\varepsilon))$ trees, where the $O_d$ notation suppresses terms that depend solely on the dimension~$d$. The running time of their construction is $O_d(n \log n \cdot \frac{\log(1/\varepsilon)}{\varepsilon^{d}} + n \cdot \varepsilon^{-2d})$. Since the same point may occur in multiple levels of the tree, the $\textit{maximum degree}$ of a point in the tree cover may be as large as $Ω(\log Φ)$, where $Φ$ is the aspect ratio of the input point set. In this work we present a $(1+\varepsilon)$-stretch tree cover with $O_d(\varepsilon^{-d+1} \cdot \log(1/\varepsilon))$ trees, which is optimal (up to the $\log(1/\varepsilon)$ factor). Moreover, the maximum degree of points in any tree is an $\textit{absolute constant}$ for any $d$. As a direct corollary, we obtain an optimal {routing scheme} in low-dimensional Euclidean spaces. We also present a $(1+\varepsilon)$-stretch $\textit{Steiner}$ tree cover (that may use Steiner points) with $O_d(\varepsilon^{(-d+1)/{2}} \cdot \log(1/\varepsilon))$ trees, which too is optimal. The running time of our two constructions is linear in the number of edges in the respective tree covers, ignoring an additive $O_d(n \log n)$ term; this improves over the running time underlying the Dumbbell Theorem.

Euclidean spanners are important geometric objects that have been extensively studied since the 1980s. The two most basic “compactness” measures of a Euclidean spanner$E$12We shall identify a graph$H = (X,E)$with its edge set$E$. All edge weights are given by the Euclidean distances. are the size (number of edges)$\vert E\vert$and the weight (sum of edge weights)$\Vert E\Vert$. The state-of-the-art constructions of Euclidean$(1+\epsilon)$-spanners in$\mathbb{R}^{d}$have$o_{d}(_{n\cdot\epsilon^{-d+1}})$edges (or sparsity$O_{d}(\epsilon^{-d+1}))$and weight$O_{d}(\epsilon^{-d} \log \epsilon^{-1}) \cdot\Vert E_{\text{mst}}\Vert$(or lightness$O_{d}(\epsilon^{-d}\log\epsilon^{-1}))$; here$O_{d}$suppresses a factor of$d^{O(d)}$and$\Vert E_{\text{mst}}\Vert$denotes the weight of a minimum spanning tree of the input point set. Importantly, these two upper bounds are (near-)optimal (up to the$d^{O(d)}$factor and disregarding the factor of$\log(\epsilon^{-1})$in the lightness bound) for some extremal instances [Le and Solomon, 2019], and therefore they are (near-)optimal in an existential sense. Moreover, both these upper bounds are attained by the same construction-the classic greedy spanner, whose sparsity and lightness are not only existentially optimal, but they also significantly outperform those of any other Euclidean spanner construction studied in an experimental study by [Farshi-Gudmundsson, 2009] for various practical point sets in the plane. This raises the natural question of whether the greedy spanner is (near-) optimal for any point set instance? Motivated by this question, we initiate the study of instance optimal Euclidean spanners. Our results are two-fold. •Rather surprisingly (given the aforementioned experimental study), we demonstrate that the greedy spanner is far from being instance optimal, even when allowing its stretch to grow. More concretely, we design two hard instances of point sets in the plane, where the greedy$(1+x\epsilon)$-spanner (for basically any parameter$x \geq 1$) has$\Omega_{x}(\epsilon^{-1/2})\cdot\vert E_{\text{spa}} \vert$edges and weight$\Omega_{x}(\epsilon^{-1})\cdot\Vert E_{\text{light}}\Vert$, where$E_{\text{spa}}$and$E_{\text{light}}$denote the per-instance sparsest and lightest$(1 +\epsilon)$-spanners, respectively, and the$\Omega_{x}$notation suppresses a polynomial dependence on$1/x$. •As our main contribution, we design a new construction of Euclidean spanners, which is inherently different from known constructions, achieving the following bounds: a stretch of$1+\epsilon\cdot 2^{O(\log^{*}(d/\epsilon)}$with$O(1)\cdot\vert E_{\text{spa}}\vert$edges and weight$O(1)$. $\Vert E_{ \text{light}}\Vert$. In other words, we show that a slight increase to the stretch suffices for obtaining instance optimality up to an absolute constant for both sparsity and lightness. Remarkably, there is only a log-star dependence on the dimension in the stretch, and there is no dependence on it whatsoever in the number of edges and weight. In general, for any integer$k\geq 1$, we can construct a Euclidean spanner in$\mathbb{R}^{d}$of stretch$1+\epsilon\cdot 2^{O(k)}$with$O(\log^{(k)}(\epsilon^{-1})+\log^{(k-1)}(d))\cdot\vert E_{\text{spa}}\vert$edges and weight$O(\log^{(k)}(\epsilon^{-1})+\log^{(k-1)}(d))\cdot\Vert E_{\text{light}}\Vert$, where$\log^{(k)}$denotes the k-iterated logarithm.

We consider the problem of estimating the size of a maximum matching in low-arboricity graphs in the dynamic graph stream model. In this setting, an algorithm with limited memory makes multiple passes over a stream of edge insertions and deletions, resulting in a low-arboricity graph. Let n be the number of vertices of the input graph, and α be its arboricity. We give the following results. 1) As our main result, we give a three-pass streaming algorithm that produces an (α + 2)(1 + ε)-approximation and uses space O(ε^{-2}⋅α²⋅n^{1/2}⋅log n). This result should be contrasted with the Ω(α^{-5/2}⋅n^{1/2}) space lower bound established by [Assadi et al., SODA'17] for one-pass algorithms, showing that, for graphs of constant arboricity, the one-pass space lower bound can be achieved in three passes (up to poly-logarithmic factors). Furthermore, we obtain a two-pass algorithm that uses space O(ε^{-2}⋅α²⋅n^{3/5}⋅log n). 2) We also give a (1+ε)-approximation multi-pass algorithm, where the space used is parameterized by an upper bound on the size of a largest matching. For example, using O(log log n) passes, the space required is O(ε^{-1}⋅α²⋅k⋅log n), where k denotes an upper bound on the size of a largest matching. Finally, we define a notion of arboricity in the context of matrices. This is a natural measure of the sparsity of a matrix that is more nuanced than simply bounding the total number of nonzero entries, but less restrictive than bounding the number of nonzero entries in each row and column. For such matrices, we exploit our results on estimating matching size to present upper bounds for the problem of rank estimation in the dynamic data stream model.

The notion of shortcut partition, introduced recently by Chang, Conroy, Le, Milenković, Solomon, and Than [CCL+23], is a new type of graph partition into low-diameter clusters. Roughly speaking, the shortcut partition guarantees that for every two vertices u and v in the graph, there exists a path between u and v that intersects only a few clusters. They proved that any planar graph admits a shortcut partition and gave several applications, including a construction of tree cover for arbitrary planar graphs with stretch 1 + ɛ and O(1) many trees for any fixed ɛ ∈ (0,1). However, the construction heavily exploits planarity in multiple steps, and is thus inherently limited to planar graphs.

The greedy spanner in a low-dimensional Euclidean space is a fundamental geometric construction that has been extensively studied over three decades, as it possesses the two most basic properties of a good spanner: constant maximum degree and constant lightness. Recently, Eppstein and Khodabandeh [ 28 ] showed that the greedy spanner in \(\mathbb {R}^2\) admits a sublinear separator in a strong sense: Any subgraph of k vertices of the greedy spanner in \(\mathbb {R}^2\) has a separator of size \(O(\sqrt {k})\) . Their technique is inherently planar and is not extensible to higher dimensions. They left showing the existence of a small separator for the greedy spanner in \(\mathbb {R}^d\) for any constant d ≥ 3 as an open problem. In this article, we resolve the problem of Eppstein and Khodabandeh [ 28 ] by showing that any subgraph of k vertices of the greedy spanner in \(\mathbb {R}^d\) has a separator of size \(O(k^{1-1/d})\) . We introduce a new technique that gives a simple criterion for any geometric graph to have a sublinear separator that we dub τ-lanky : A geometric graph is τ-lanky if any ball of radius r cuts at most τ edges of length at least r in the graph. We show that any τ-lanky geometric graph of n vertices in \(\mathbb {R}^d\) has a separator of size \(O(\tau n^{1-1/d})\) . We then derive our main result by showing that the greedy spanner is O (1)-lanky. We indeed obtain a more general result that applies to unit ball graphs and point sets of low fractal dimensions in \(\mathbb {R}^d\) . Our technique naturally extends to doubling metrics. We use the τ-lanky criterion to show that there exists a (1+ε)-spanner for doubling metrics of dimension d with a constant maximum degree and a separator of size \(O(n^{1-\frac{1}{d}})\) ; this result resolves an open problem posed by Abam and Har-Peled [ 1 ] a decade ago. We then introduce another simple criterion for a graph in doubling metrics of dimension d to have a sublinear separator. We use the new criterion to show that the greedy spanner of an n -point metric space of doubling dimension d has a separator of size \(O((n^{1-\frac{1}{d}}) + \log \Delta)\) where Δ is the spread of the metric; the factor log (Δ) is tightly connected to the fact that, unlike its Euclidean counterpart, the greedy spanner in doubling metrics has unbounded maximum degree . Finally, we discuss algorithmic implications of our results.

While research on the geometry of planar graphs has been active in the past decades, many properties of planar metrics remain mysterious. This paper studies a fundamental aspect of the planar graph geometry: covering planar metrics by a small collection of simpler metrics. Specifically, a tree cover of a metric space $(X, \delta)$ is a collection of trees, so that every pair of points u and v in X has a low-distortion path in at least one of the trees.The celebrated “Dumbbell Theorem” [ADM+95] states that any low-dimensional Euclidean space admits a tree cover with $O(1)$ trees and distortion $1+\varepsilon$, for any fixed $\varepsilon \in(0,1)$. This result has found numerous algorithmic applications, and has been generalized to the wider family of doubling metrics [BFN19]. Does the same result hold for planar metrics? A positive answer would add another evidence to the well-observed connection between Euclidean/doubling metrics and planar metrics.In this work, we answer this fundamental question affirmatively. Specifically, we show that for any given fixed $\varepsilon \in(0,1)$, any planar metric can be covered by $O(1)$ trees with distortion $1+\varepsilon$. Our result for planar metrics follows from a rather general framework: First we reduce the problem to constructing tree covers with additive distortion. Then we introduce the notion of shortcut partition, and draw connection between shortcut partition and additive tree cover. Finally we prove the existence of shortcut partition for any planar metric, using new insights regarding the grid-like structure of planar graphs. To demonstrate the power of our framework:•We establish additional tree cover results beyond planar metrics; in particular, we present an $O(1)$-size tree cover with distortion $1+\varepsilon$ for bounded treewidth metrics;•We obtain several algorithmic applications in planar graphs from our tree cover. The grid-like structure is a technical contribution that we believe is of independent interest. We showcase its applicability beyond tree cover by constructing a simpler and better embedding of planar graphs into $O(1)$-treewidth graphs with small additive distortion, resolving an open problem in this line of research.

An essential requirement of spanners in many applications is to be fault-tolerant: a $(1+\epsilon)$-spanner of a metric space is called (vertex) f-fault-tolerant $(f-F T)$ if it remains a $(1+\epsilon)$-spanner (for the non-faulty points) when up to f faulty points are removed from the spanner. Fault-tolerant (FT) spanners for Euclidean and doubling metrics have been extensively studied since the 90 s. For low-dimensional Euclidean metrics, Czumaj and Zhao in SoCG’03 [CZ03] showed that the optimal guarantees $O(f n), O(f)$ and $O\left(f^{2}\right)$ on the size, degree and lightness of f-FT spanners can be achieved via a greedy algorithm, which naïvely runs in $O\left(n^{3}\right) \cdot 2^{O(f)}$ time.$^{1}$ An earlier construction, by Levcopoulos et al. [LNS98] from STOC’98, has a faster running time of $O(n \log n)+n 2^{O(f)}$, but has a slack of $2^{\Omega(f)}$ in all the three involved parameters. The question of whether the optimal bounds of [CZ03] can be achieved via a fast construction has remained elusive, with the lightness parameter being the bottleneck: Any construction (other than [CZ03]) has lightness either $2^{\Omega(f)}$ or $\Omega(\log n)$. Moreover, in the wider family of doubling metrics, it is not even clear whether there exists an f FT spanner with lightness that depends solely on f (even exponentially): all existing constructions have lightness $\Omega(\log n)$ since they are built on the net-tree spanner, which is induced by a hierarchical net-tree of lightness $\Omega(\log n)$. In this paper we settle in the affirmative these longstanding open questions. Specifically, we design a construction of f-FT spanners that is optimal with respect to all the involved parameters (size, degree, lightness and running time): For any n-point doubling metric, any $\epsilon\gt0$, and any integer $1 \le \log f n\le + {nfn}-)$, an2, our construction provides,-spanner with within time $O(n$ size $O (fn)$, degree $O(f)$ and lightness $O(f^{2})$. To break the $\Omega (\log n)$ lightness barrier, we introduce a new geometric object — the light net-forest. Like the net-tree, the light net-forest is induced by a hierarchy of nets. However, to ensure small lightness, the light net-forest is inherently less “well-connected” than the net-tree, which, in turn, makes the task of achieving fault-tolerance significantly more challenging. Further, to achieve the optimal degree (and size) together with optimal lightness, and to do so within the optimal running time — we overcome several highly nontrivial technical challenges.

The greedy spanner in a low dimensional Euclidean space is a fundamental geometric construction that has been extensively studied over three decades as it possesses the two most basic properties of a good spanner: constant maximum degree and constant lightness. Recently, Eppstein and Khodabandeh [EK21] showed that the greedy spanner in ℝ2 admits a sublinear separator in a strong sense: any subgraph of k vertices of the greedy spanner in ℝ2 has a separator of size . Their technique is inherently planar and is not extensible to higher dimensions. They left showing the existence of a small separator for the greedy spanner in ℝd for any constant d ≥ 3 as an open problem. In this paper, we resolve the problem of Eppstein and Khodabandeh [EK21] by showing that any subgraph of k vertices of the greedy spanner in ℝd has a separator of size O(k1–1/d). We introduce a new technique that gives a simple criterion for any geometric graph to have a sublinear separator that we dub τ-lanky: a geometric graph is τ-lanky if any ball of radius r cuts at most τ edges of length at least r in the graph. We show that any τ-lanky geometric graph of n vertices in ℝd has a separator of size O(τn1–1/d). We then derive our main result by showing that the greedy spanner is O(1)-lanky. We indeed obtain a more general result that applies to unit ball graphs and point sets of low fractal dimensions in ℝd. Our technique naturally extends to doubling metrics. We use the τ-lanky criterion to show that there exists a (1 + ∊)-spanner for doubling metrics of dimension d with a constant maximum degree and a separator of size ; this result resolves an open problem posed by Abam and Har-Peled [AHP10] a decade ago. We then introduce another simple criterion for a graph in doubling metrics of dimension d to have a sublinear separator. We use the new criterion to show that the greedy spanner of an n-point metric space of doubling dimension d has a separator of size where Δ is the spread of the metric; the factor log(Δ) is tightly connected to the fact that, unlike its Euclidean counterpart, the greedy spanner in doubling metrics has unbounded maximum degree. Finally, we discuss algorithmic implications of our results.

In a 1997 seminal paper, W. Maddison proposed minimizing deep coalescences, or MDC, as an optimization criterion for inferring the species tree from a set of incongruent gene trees, assuming the incongruence is exclusively due to lineage sorting. In a subsequent paper, Maddison and Knowles provided and implemented a search heuristic for optimizing the MDC criterion, given a set of gene trees. However, the heuristic is not guaranteed to compute optimal solutions, and its hill-climbing search makes it slow in practice. In this paper, we provide two exact solutions to the problem of inferring the species tree from a set of gene trees under the MDC criterion. In other words, our solutions are guaranteed to find the tree that minimizes the total number of deep coalescences from a set of gene trees. One solution is based on a novel integer linear programming (ILP) formulation, and another is based on a simple dynamic programming (DP) approach. Powerful ILP solvers, such as CPLEX, make the first solution appealing, particularly for very large-scale instances of the problem, whereas the DP-based solution eliminates dependence on proprietary tools, and its simplicity makes it easy to integrate with other genomic events that may cause gene tree incongruence. Using the exact solutions, we analyze a data set of 106 loci from eight yeast species, a data set of 268 loci from eight Apicomplexan species, and several simulated data sets. We show that the MDC criterion provides very accurate estimates of the species tree topologies, and that our solutions are very fast, thus allowing for the accurate analysis of genome-scale data sets. Further, the efficiency of the solutions allow for quick exploration of sub-optimal solutions, which is important for a parsimony-based criterion such as MDC, as we show. We show that searching for the species tree in the compatibility graph of the clusters induced by the gene trees may be sufficient in practice, a finding that helps ameliorate the computational requirements of optimization solutions. Further, we study the statistical consistency and convergence rate of the MDC criterion, as well as its optimality in inferring the species tree. Finally, we show how our solutions can be used to identify potential horizontal gene transfer events that may have caused some of the incongruence in the data, thus augmenting Maddison's original framework. We have implemented our solutions in the PhyloNet software package, which is freely available at: http://bioinfo.cs.rice.edu/phylonet.

MOTIVATION: In bacterial evolution, inferring a strain tree, which is the evolutionary history of different strains of the same bacterium, plays a major role in analyzing and understanding the evolution of strongly isolated populations, population divergence and various evolutionary events, such as horizontal gene transfer and homologous recombination. Inferring a strain tree from multilocus data of these strains is exceptionally hard since, at this scale of evolution, processes such as homologous recombination result in a very high degree of gene tree incongruence. RESULTS: In this article we present a novel computational method for inferring the strain tree despite massive gene tree incongruence caused by homologous recombination. Our method operates in three phases, where in phase I a set of candidate strain-tree topologies is computed using the maximal cliques concept, in phase II divergence times for each of the topologies are estimated using mixed integer linear programming (MILP) and in phase III the optimal tree (or trees) is selected based on an optimality criterion. We have analyzed 1898 genes from nine strains of the Staphylococcus aureus bacteria, and identified a fully resolved (binary) strain tree with estimated divergence times, despite the high degrees of sequence identity at the nucleotide level and gene tree incongruence. Our method's efficiency makes it particularly suitable for analysis of genome-scale datasets, including those of strongly isolated populations which are usually very challenging to analyze. AVAILABILITY: We have implemented the algorithms in the PhyloNet software package, which is available publicly at http://bioinfo.cs.rice.edu/phylonet/.

BACKGROUND: Phylogenies, i.e., the evolutionary histories of groups of taxa, play a major role in representing the interrelationships among biological entities. Many software tools for reconstructing and evaluating such phylogenies have been proposed, almost all of which assume the underlying evolutionary history to be a tree. While trees give a satisfactory first-order approximation for many families of organisms, other families exhibit evolutionary mechanisms that cannot be represented by trees. Processes such as horizontal gene transfer (HGT), hybrid speciation, and interspecific recombination, collectively referred to as reticulate evolutionary events, result in networks, rather than trees, of relationships. Various software tools have been recently developed to analyze reticulate evolutionary relationships, which include SplitsTree4, LatTrans, EEEP, HorizStory, and T-REX. RESULTS: In this paper, we report on the PhyloNet software package, which is a suite of tools for analyzing reticulate evolutionary relationships, or evolutionary networks, which are rooted, directed, acyclic graphs, leaf-labeled by a set of taxa. These tools can be classified into four categories: (1) evolutionary network representation: reading/writing evolutionary networks in a newly devised compact form; (2) evolutionary network characterization: analyzing evolutionary networks in terms of three basic building blocks - trees, clusters, and tripartitions; (3) evolutionary network comparison: comparing two evolutionary networks in terms of topological dissimilarities, as well as fitness to sequence evolution under a maximum parsimony criterion; and (4) evolutionary network reconstruction: reconstructing an evolutionary network from a species tree and a set of gene trees. CONCLUSION: The software package, PhyloNet, offers an array of utilities to allow for efficient and accurate analysis of evolutionary networks. The software package will help significantly in analyzing large data sets, as well as in studying the performance of evolutionary network reconstruction methods. Further, the software package supports the proposed eNewick format for compact representation of evolutionary networks, a feature that allows for efficient interoperability of evolutionary network software tools. Currently, all utilities in PhyloNet are invoked on the command line.