From combinatorial embedding to DCEL in linear time

Question

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:

1. start with an edge $uv$,
2. find vertex $v$ in $Adj(u)$,
3. get the vertex $w$ after $v$ in $Adj(v)$
4. set $next(uv) \leftarrow vw$
5. 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$:

1. The head vertex $u$ of $e$,
2. The tail vertex $v$ of $e$,
3. The face left of $e$ (where `left' is relative to the orientation $u \to v$),
4. The face right of $e$,
5. A pointer $prev(uv)$ which points to the edge incident with $u$ that is anticlockwise from $uv$ around $u$,
6. 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.

Answer 1

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:

1. Loop through all vertices $u$.

2. 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.