New length bounds for cycle bases

Based on a recent work by Abraham, Bartal and Neiman (2007), we construct a strictly fundamental cycle basis of length 0(n(2)) for any unweighted graph, whence proving the conjecture of Deo et al. (1982). For weighted graphs, we construct cycle bases of length O(W - log n log log n), where W denotes the sum of the weights of the edges. This improves the upper bound that follows from the result of Elkin et al. (2005) by a logarithmic factor and, for comparison from below, some natural classes of large girth graphs are known to exhibit minimum cycle bases of length Q (W - log n). We achieve this bound for weighted graphs by not restricting ourselves to strictly fundamental cycle bases-as it is inherent to the approach of Elkin et al-but rather also considering weakly fundamental cycle bases in our construction. This way we profit from some nice properties of Hierarchically Well-Separated Trees that were introduced by Bartal (1998). (C) 2007 Elsevier B.V. All rights reserved.