What is a "graph carving"?

Question

Hey guys,

I've faved a question here, and the most promising answer to-date implies "graph carvings". Problem is, I have no clue what it is (neither does the OP, apparently), and it sounds very promising and interesting for several uses. My Googlefu failed me on this topic, as I found no useful/free resource talking about them.

Can someone please tell me what is a 'graph carving', how I can make one for a graph, and how I can determine what makes a certain carving better suited for a task than another?

Please don't go too mathematical on me (or be ready to answer more questions): I understand what's a graph, what's a node and what's a vertex, I manage with big O notation, but I have no real maths background.

Answer 1

I think the answer given in the linked question is a little loose with terminology. I think it is describing a tree carving of a graph G. This is still not particularly google-friendly, I admit, but perhaps it will get you going on your way. The main application of this structure appears to be in one particular DFS algorithm, described in these two papers.

A possibly more clear description of the same algorithm may appear in this book.

I'm not sure stepping through this algorithm would be particularly helpful. It is a reasonably complex algorithm and the explanation would probably just parrot those given in the papers I linked. I can't claim to understand it very well myself. Perhaps the most fruitful approach would be to look at the common elements of those three links, and post specific questions about parts you don't understand.