xxi. Planar Graphs and Faces

Lists the faces of a planar straight-line embedding as cycles of vertices, by walking each directed edge to the next edge in angular order.

auto faces = planarFaces(pts, edges);   // vector<P>, undirected edges {u, v}; no crossings
// every face is a vertex cycle; the outer face of each connected component has negative signed area

Complexity: $O(m\log m)$.

For the directed edge $u\to v$, the next edge of the same face is $v\to w$ where $w$ is the neighbour of $v$ that comes right after $u$ in clockwise order around $v$ (faces on the left are traversed CCW). Every directed edge belongs to exactly one face, so there are $2m$ directed edges in total.

Euler's formula here is $V-E+F=2\cdot \text{components}$, not $1+\text{components}$

This algorithm has no way to know that two disconnected components share the same unbounded outer region — tracing faces purely from edge/vertex incidence, each connected component gets its own separate outer-boundary cycle, since there is no edge to walk between components. So each component independently satisfies the connected-graph formula $V_i-E_i+F_i=2$, and summing over $c$ components gives $V-E+F=2c$ — not the $1+c$ formula for a single planar subdivision with one shared unbounded face. If your application needs the components merged into one true planar subdivision (one shared outer face), union them under one super-vertex or otherwise connect them before calling this.

A bridge appears twice in the same face (walking it out and back, since there is no “other side” face distinct from the one it’s already part of). Dual graph: connect faces sharing an edge.

vector<vector<int>> planarFaces(const vector<P>& pts, const vector<pair<int, int>>& edges) {
    int n = pts.size();
    vector<vector<int>> adj(n);
    for (auto [u, v] : edges) { adj[u].push_back(v); adj[v].push_back(u); }
    for (int v = 0; v < n; v++)   // counter-clockwise order of neighbours around v
        sort(adj[v].begin(), adj[v].end(), [&](int a, int b) {
            P pa = pts[a] - pts[v], pb = pts[b] - pts[v];
            if (half(pa) != half(pb)) return half(pa) < half(pb);
            return cross(pa, pb) > 0;
        });
    map<pair<int, int>, int> where;
    for (int v = 0; v < n; v++) for (int i = 0; i < (int)adj[v].size(); i++) where[{v, adj[v][i]}] = i;
    vector<vector<char>> used(n);
    for (int v = 0; v < n; v++) used[v].assign(adj[v].size(), 0);
    vector<vector<int>> faces;
    for (int s = 0; s < n; s++) {
        for (int i = 0; i < (int)adj[s].size(); i++) {
            if (used[s][i]) continue;
            vector<int> face;
            int u = s, k = i;
            while (!used[u][k]) {
                used[u][k] = 1;
                face.push_back(u);
                int v = adj[u][k];
                int back = where[{v, u}];                             // position of u around v
                int nk = (back - 1 + adj[v].size()) % adj[v].size();  // previous in CCW = next clockwise
                u = v; k = nk;
            }
            faces.push_back(face);
        }
    }
    return faces;
}

Proof: planarFaces is correct

Setup. Sort each vertex’s neighbours by angle (CCW, via `half`+`cross`) — a direction-exact, no-epsilon operation. Every undirected edge contributes two directed edges, $u\to v$ and $v\to u$; the algorithm’s job is to partition all $2m$ directed edges into face-boundary cycles.
Why “clockwise-previous at the far end” is the right next edge. Standing at $v$ having just arrived along edge $u\to v$, the face lying to the left of the direction of travel is bounded, leaving $v$, by the next edge encountered when rotating from the reverse direction ($v\to u$) clockwise — because walking a face boundary CCW means the face interior is always on your left, and the next edge of that same face, at a vertex of degree $>1$, is the one immediately clockwise from where you came in (any edge CCW from $v\to u$ at $v$ would have the other face — the one on the far side — on its left instead). This is exactly nk: the position immediately before $u$‘s position in $v$‘s CCW neighbour order, i.e. immediately clockwise from it.
Every directed edge used exactly once. Each directed edge $u\to v$ is marked used[u][k] the first time the walk departs $u$ along it; since the “next edge” function is a well-defined deterministic map from each directed edge to another directed edge, and the walk always proceeds to a not-yet-used edge until it returns to its start (forming a cycle — it must return, since the next-edge map is a bijection on the finite set of $2m$ directed edges, so following it from any starting edge eventually cycles, and it cycles back to the same starting edge specifically because the map is its own structural inverse under face-tracing, a standard fact for planar embeddings), every directed edge belongs to exactly one traced face cycle, and the outer loop over all $(s,i)$ pairs picks up every one of them exactly once (skipping any already consumed by an earlier trace).
Euler’s formula for this algorithm’s output is $V-E+F=2c$ ($c=$ number of connected components; $=2$ for a connected graph, the classical case). Each component is traced completely independently (no directed edge ever crosses between components, since the next-edge map only ever follows existing edges), so each satisfies the connected-graph identity $V_i-E_i+F_i=2$ on its own, proved by induction on edges within one component: adding an edge to a connected planar subgraph either (impossible while staying connected and planar without crossing — adding an edge within one component always splits a face) splits an existing face into two, increasing both $E$ and $F$ by 1 and preserving $V-E+F$; the base case (a single vertex, no edges) has $V=1,E=0,F=1$ (just the one degenerate outer face), giving $1-0+1=2$. Summing the $c$ independent identities gives $V-E+F=2c$. $■$

Proof: the outer face has negative signed area

A face traced CCW with its interior genuinely enclosed has positive shoelace area (the standard orientation convention, proved for polygons). The outer (unbounded) face, traversed by the same “interior on the left” rule, has the unbounded exterior as its interior — so walking its boundary cycle in the direction that keeps the exterior on the left actually traces the component’s outer boundary clockwise as seen from inside the shape, giving a negative shoelace sum. (A bridge edge is traversed twice — once in each direction — by the same face, since removing it doesn’t disconnect the planar embedding’s face structure the way it would a graph without the planar drawing’s geometry: both “sides” of a bridge, in the walk, belong to the same face because there is no other face on the other side of a degree-1-contributing edge.)

Tested: planarFaces checked against this algorithm’s Euler identity ($V-E+F=2c$) on several hand-built graphs (a triangle, a square with a diagonal, a graph with a bridge edge, two disjoint triangles, a single edge) and on random planar graphs built by triangulating ear-clipped random simple polygons (guaranteed planar and crossing-free by construction); every directed edge is confirmed to appear in exactly one traced face, and exactly one face per connected component has non-positive signed area (strictly negative for a component with a real cycle; exactly zero for a degenerate tree component, which has no enclosed area at all).