Prof. Michael Elkin

Based on a recent work by Abraham, Bartal and Neiman (2007), we construct a strictly fundamental cycle basis of length O (n²) 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 Ω (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).