The idea for this problem comes from GATE CS 2014 Set-3 Q13.
Given a graph, are there any heuristics to figure out a DFS traversal which has minimum/maximum recursion depth?
Consider the graph from the question, labelled
Consider the DFS traversal a-b-c-f-e-d-g-h-i-j-k-l-m-n-q-p-o-r-s-t-u with a recursion depth of 19. The numbers represent the recursion depth as per the question
Now consider the traversal j-k-l-m-p-s-r-o-t-q-u-n-i-f-e-d-a-b-c-g-h, which has a recursion depth of 8.
While it is easy to figure this out for a small enough graph and on paper, I am struggling to find a well defined algorithm/heuristic to do so. My intuition in minimizing was to find an articulation point in the graph which would split it into the maximum number of subgraphs(hence j as a starting vertex), and for maximizing, a node with minimum degree which is not adjacent to an articulation point(hence discarding k and u and selecting a as starting vertex but any other similar vertex would do).
Is there a name for this problem, and any approaches to solve(other than brute force)?