Question: Figure 2 shows a graph G , with a given DFS ordering of the vertices. On the right side of the figure, the palm tree

Figure 2 shows a graph G, with a given DFS ordering of the vertices. On the right side of the figure, the palm tree is drawn according to the first part of Tarjan-Hopcroft algorithm for planarity testing.
a) If we follow the DFS ordering, which vertex v has the first frond back to the root (vertex 1)?
b) Let C be the cycle 1,2,..., v (the vertex v is found in 3(a)). if we remove the edges of cycle C, what are the connected components (Gi for i =1,2,...) we get? Draw them.
c) For each Gi from 3(b), add the cycle C to it to construct G i . Draw all the G i s.
PLEASE NOTE THE ANSWER TOO A) IS VERTEX 5
PLEASE ANSWER B AND C ACCORDINGLY
 Figure 2 shows a graph G, with a given DFS ordering

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer
Step: 1 Unlock blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Databases Questions!