Find a dual graph

Question

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:

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.

Answer 1

Python3, 416 bytes:

S=sorted
T=tuple
def C(n,o,l,p=[]):
 if n==o and p:yield T(map(T,S(p)));return
 for i in l[n]:
  if(s:=S([n,i]))not in p:yield from C(i,o,l,p+[s])
def f(e):
 K,s=0,{min(r,key=len)for i in e if(r:=[*C(i,i,e)])}
 if not s and e:return[(0,0)]
 E={(K:=K+1):set(i) for i in s}
 l=[((a,b),j)for a in E for b in E if a<b and(j:=E[a]&E[b])]
 return[(0,i)for i in E for _ in E[i]-{x for _,y in l for x in y}]+[a for a,_ in l]

Try it online!