# How to quantify the tree-like-ness of a graph?

What are good measures of tree-like-ness of a graph and algorithms for calculating them?

• There are many ways to measure the "tree-like-ness" of a graph. Which property of the tree would you like to preserve? Jul 4 '11 at 2:03
• I'm not exactly sure. Since trees don't have cycles, the number and length of cycles in a graph would seem to be a good negative measure of "tree-like-ness". But (if we consider directed trees), uni-directionality also seems like an important characteristic of trees. For instance, I would like a measure that says that a graph is highly tree-like if it's a highly overlapping heterarchy with only two top-level nodes, and if directed, a particular dominant (but not necessarily universal) directionality. Jul 4 '11 at 2:37
• Have a look at en.wikipedia.org/wiki/Tree_decomposition Jul 4 '11 at 6:06
• Based on the comment, it sounds like you are interested in graphs that resemble an arborescence, i.e., a directed rooted tree in which all edges point away from the root node. (In general, a directed tree does not necessarily have any "dominant directionality".) Jul 4 '11 at 9:42