How to find an ordering of edges incident on a fixed vertex in a plane embedding?

Question

Suppose that we have a plane embedding $G$. Let $v$ be a vertex in $G$ with degree $d$. There exist an ordering $u_1,u_2,\ldots,u_d$ of neighbors of $v$ such that the graph is still a plane embedding if we add a cycle $u_1-u_2-\ldots-u_d-u_1$ to $G$ (The cyclic ordering of neighbors of $v$ is such an ordering).
Is there an algorithm to find such an ordering whose running time is polynomial in $d$?
If we test every possible ordering, the running time will be $O(d!)$. I thought i had an algorithm, but then someone proposed another algorithm to me. The proposed algorithm is to start with a neighbor (call it $u_1$), for every other neighbor, test if adding edge joining $u_1$ to it preserves planarity (if yes, call that neighbor as $u_2$ and add edge $u_1u_2$) and so on, and finally join $u_d$ to $u_1$. But this algorithm will not work as shown in the figure.

My idea is shown in figure below.

But now I feel like this method might also face similar problems like the proposed algorithm. Is this a correct algorithm? Note: the usage of cyclic ordering of edges incident of a vertex is common. I meant the same when i said cyclic ordering of neighbours of a vertex.

Answer 1

(Disclaimer: This answer is given by someone not in se)

Use faces of the graph to find the cyclic ordering of edges incident on $v$. For example, let the set of edges incident on $v$ be $E_0=\{e_1,e_2,\ldots,e_d\}$. Then find the dual $G^*$ of $G$ and take the induced subgraph $G^*[F_0]$ where $F_0$ is the set of faces that contain $v$ as a vertex. The induced subgraph must be a cycle and it gives us a cyclic ordering of the edges $e_i\in E_0$ (we have a cylcic ordering of faces. Take edge common to each parir of nearby faces in that ordering).

Clearly cyclic ordering of edges incident on $v$ gives us a 'cyclic ordering' of neighbours of $v$.