# algorithm to find complementary spanning tree in dual graph

I have read from wikipedia, that for every spanning tree in a graph [primal] we have a spanning tree in the dual graph which consists of dual of the complementary set of edges [edges not used in the original spanning tree].

the spanning tree in the primal graph has V-1 edges and the spanning tree in the dual graph has F-1 edges. This also leads to a simple derivation of Euler's formula, As total edges in the graph, E = (V-1) + (F-1) .

Given the set of all edges and a spanning tree, we need an algorithm to find the complementary spanning tree in the dual graph.

What is needed : 1. find the complementary set of edges. 2. find dual of each edge.

I am not able to find faces pertaining to dual of an edge.

Edit : i am only considering planar graphs

• Can you clarify what it is that you don't understand yet. I sense that it's the definition of the dual of a graph but I may be wrong. – Kai Nov 9 at 13:01
• I don't understand how to identify the two faces that connect the dual of an edge. I understand the definition of the dual of a graph and dual of an edge. More specifically, i can't come up with an algorithm to do that. – Nidheesh Nov 9 at 13:11
• If you understand how to construct the dual of a plane graph, I'd expect you'd have understood how to construct each of its edges. – Kai Nov 9 at 13:22
• I haven't understood the algorithm for that either. Given problem is same with less number of edges. – Nidheesh Nov 9 at 13:36
• How is your input graph represented? (It better be a plane graph, not just a planar one that lacks the embedding information.) – Kai Nov 10 at 5:14