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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.