6
\$\begingroup\$

A dual graph is defined such that for every "face" in a graph G, there is a corresponding vertex in the dual graph, and for every edge on the graph G, there is an edge in the dual graph connecting the vertices corresponding to the two faces on either side of the edge of the original graph. Note that the faces on both side may be the same face, for example the graph consisting of 2 vertices connected by a single edge (see case 3).

Here is a shamelessly borrowed example from Wikipedia:

enter image description here

Your goal is given a graph, find a dual graph for that graph. Note that there may not necessarily be a unique dual graph for a given graph; you need only find one. Assume all input graphs are undirected and planar.

Input

Assume all vertices of the input graph have some consecutive integer numbering starting at any beginning integer value of your choice. An edge is described by an unordered pair of integers denoting the vertices the edge connects. For example, the blue graph shown above could be described with the following unordered multiset of edges (assuming the numbering of vertices starts at 0):

[(0,1), (0,2), (1,2), (2,3), (1,3), (1,4), (4,3)]

An alternative way to describe a multigraph is via an adjacency list. Here is an example adjacency list for the above graph:

[0:(1,2), 1:(0,2,3,4), 2:(0,1,3), 3:(1,2,4), 4:(1,3)]

Your program must take as input a multigraph of edges from any source (stdio, function parameter, etc.). You may assume the input graph is connected. You may use any notation desired so long as the no additional non-trivial information is communicated to your program. For example, having an extra parameter denoting the number of input edges is perfectly acceptable, but passing in a full or partially formed dual graph as an extra parameter is not. Similarly, passing in an unordered multiset of edges, adjacency list, or adjacency matrix is fine.

Output

The output of your program should be in one of the formats allowed for the input; it needs not be the same as the input format. The output may be to any sink desired (stdio, return value, output parameter, etc.).

Examples

All following examples use unordered multisets of edges with 0-based indices. One possible output is given. As a side note, all of the test case outputs are also valid inputs for your program, and an example output is the corresponding input.

case 1:

input:
[(0,1), (0,2), (1,2), (2,3), (1,3), (1,4), (4,3)]
output:
[(0,1), (0,2), (1,0), (0,3), (0,3), (1,2), (2,3)]

case 2:

input:
[(0,1),(0,2),(1,2)]
output:
[(0,1),(0,1),(0,1)]

case 3:

input:
[(0,1)]
output:
[(0,0)]

case 4:

input:
[]
output:
[]

case 5:

input:
[(0,1),(0,2),(2,1),(3,1),(3,4),(2,4)]
output:
[(0,2),(0,2),(1,0),(1,2),(1,2),(1,2)]

Scoring

This is code golf; shortest code wins. Standard loopholes apply. You may use any built-ins not specifically designed to solve this problem.

\$\endgroup\$
  • \$\begingroup\$ Are we guaranteed the input graph is planar? \$\endgroup\$ – xnor Jul 8 '16 at 4:51
  • \$\begingroup\$ @xnor updated, yes. I also fixed case 3 since it looks like it makes more sense to allow an edge to start and end at a single vertex. \$\endgroup\$ – helloworld922 Jul 8 '16 at 4:58
  • \$\begingroup\$ Can the input have the same edge multiple times? Self loops? Isolated vertices with no edges? \$\endgroup\$ – xnor Jul 8 '16 at 5:18
  • \$\begingroup\$ yes, yes, yes*. The input must be a connected graph, so the only isolated vertices would be if a graph containing a single vertex with 0 edges (case 4). \$\endgroup\$ – helloworld922 Jul 8 '16 at 5:28
  • 1
    \$\begingroup\$ I don't know if this is formal enough, but you can choose a planar embedding, label each face with a distinct label, and then include an edge for each edge of the original graph whose vertex endpoints correspond to the faces it touches on either side. \$\endgroup\$ – xnor Jul 8 '16 at 6:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.