From combinatorial embedding to DCEL in linear time The problem:
We have a planar graph $G=(V,E)$ with $|V| = n$, given as input in the form of a combinatorial embedding.
We want to build a DCEL (doubly connected edge list) in $\mathcal{O}(n)$ time - which is apparently quite easy according to Computational Geometry: an introduction by Preparata and Shamos. This text also has a detailed explanation of the DCEL.
The difficulty (for the naive author):
Doing the "obvious" (to me at least) thing to find the $next$ "next anticlockwise edge" pointers seems to take too long (see definitions at the end of the question). The obvious thing being:

*

*start with an edge $uv$,

*find vertex $v$ in $Adj(u)$,

*get the vertex $w$ after $v$ in $Adj(v)$

*set $next(uv) \leftarrow vw$

*Repeat for all edges until we get all our pointers

The issue is step 2: this can take time $\mathcal{O}(deg(u))$, and so doing the whole process for all edges seems like it ends up taking $\mathcal{O}(n^2)$ in the worst cases.
The question:
How do we get the $next$ pointer list in $\mathcal{O}(n)$ time?

Definitions:
A combinatorial embedding of $G$ is an array of vertices $v_1, \dots, v_n$, and a collection of $n$ doubly circularly linked lists $Adj(v_i)$, where list $Adj(v_i)$ contains the neighbors of $v_i$, ordered as they would appear going anticlockwise around $v_i$. Essentially, we have an adjacency list where the order of the vertices gives a rotation system for $G$.
A DCEL is a list of edges of $G$ and a table with 6 fields per oriented edge $e=uv$:

*

*The head vertex $u$ of $e$,

*The tail vertex $v$ of $e$,

*The face left of $e$ (where `left' is relative to the orientation $u \to v$),

*The face right of $e$,

*A pointer $prev(uv)$ which points to the edge incident with $u$ that is anticlockwise from $uv$ around $u$,

*A pointer $next(uv)$ which points to the edge incident with $v$ that is anticlockwise from $uv$ around $v$.

You can also use pairs of directed edges to represent each original edge of $G$ in the DCEL and keep the definitions otherwise much the same.
 A: First, while we're building this structure, it's convenient to create the edges $uv$ in such a way that, given vertices $u$ and $v$, we can get pointers to edges $uv$ and $vu$ in $\mathcal O(1)$ time. This is not straightforward from the start because of the same searching-through-$\text{Adj}(u)$ problem. Here are two possible ways to do this as we're creating the edges:

*

*Have a hash table that maps pairs $(u,v)$ to edges.


*Have an $n \times n$ adjacency matrix where each entry is either null or a pointer to the corresponding edge. A trick like this one can spare you from taking $\mathcal O(n^2)$ time just to initialize the matrix.
If this is done, then we can create $\text{next}(uv)$ pointers in $\mathcal O(n)$ time as follows:

*

*Loop through all vertices $u$.


*For each $u$, go through $\text{Adj}(u)$ in order; whenever $w$ is the next vertex after $v$ in this cyclic list, set $\text{next}(vu) \gets vw$ (and while we're at it, set $\text{prev}(vw) \gets vu$).
Step 2 takes $\mathcal O(\deg(u))$ time, so the whole thing is $\mathcal O(n)$ time total.
