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