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

  • 1
    $\begingroup$ There are many ways to measure the "tree-like-ness" of a graph. Which property of the tree would you like to preserve? $\endgroup$ Jul 4 '11 at 2:03
  • $\begingroup$ 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. $\endgroup$
    – mwhite
    Jul 4 '11 at 2:37
  • 7
    $\begingroup$ Have a look at en.wikipedia.org/wiki/Tree_decomposition $\endgroup$ Jul 4 '11 at 6:06
  • 1
    $\begingroup$ 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".) $\endgroup$ Jul 4 '11 at 9:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.