In this article, the following question is answered: Given a cycle C, of size N, how can one compute, in O(N) time, a minimal set of edges E such that adjoining E to the cycle yields a graph with a binary spanning tree having minimal total path length? The answer is given through an algorithm for top-down construction of natural cycletrees, where the structure of each subtree is restricted by a split relation between certain properties of the subtree.

}, author = {Margus Veanes and Jonas Barklund}, journal = {Information Processing Letters}, pages = {313-318}, publisher = {Elsevier}, title = {Construction of natural cycletrees}, url = {http://research.microsoft.com/apps/pubs/default.aspx?id=78385}, volume = {60}, year = {1996}, }