Boyer‑Myrvold 平面性检测与平面嵌入算法

DFS(v):
    dfn[v] = ++time
    low[v] = dfn[v]

    for each edge e = (v, w) in adjacency list:
        if e is already processed: continue

        if w not visited:
            parent[w] = v
            mark e as tree edge
            // 1. 递归进入子树
            DFS(w)

            // 2. 合并子树的嵌入信息
            low[v] = min(low[v], low[w])

            // 3. 处理子树返回的 back edges
            //    (在子树根 w 处已经把所有 back edges插入了环序)
            //    此时只需要把 w 与 v 之间的树边加入 v 的环序
            InsertTreeEdgeIntoAdjOrder(v, w)

        else if dfn[w] < dfn[v] and w != parent[v]:
            // 发现 back edge (v,w) 向上指向祖先
            low[v] = min(low[v], dfn[w])
            mark e as back edge

            // 4. 把 back edge 插入当前面
            InsertBackEdgeIntoAdjOrder(v, w)

struct AdjNode {
    int neighbor;               // 邻居编号
    list<AdjNode>::iterator it; // 在该顶点的环序链表中的位置
    Edge* rev;                  // 指向对方方向的 Edge
    bool processed;            // 是否已加入嵌入
};

vector<list<AdjNode>> adjOrder(n); // 每个顶点的环序

struct EmbedOp {
    int u, v;               // 边的两个端点
    list<AdjNode>::iterator uPos, vPos; // 插入时的迭代器（用于回滚）
    int faceID;            // 所属面标识
};

stack<EmbedOp> embedStack;

struct SepPair {
    int a, b;          // 两条相邻 back edge 的端点
    vector<int> verts; // 受影响的顶点集合（子图）
};

stack<SepPair> sepStack;

int time = 0;
vector<int> dfn(n, 0), low(n, 0), parent(n, -1);
vector<bool> visited(n, false);
vector<list<AdjNode>> adjOrder(n);
stack<EmbedOp> embedStack;
stack<SepPair> sepStack;

void DFS(int v) {
    visited[v] = true;
    dfn[v] = low[v] = ++time;

    for (Edge* e : edgesFrom(v)) {
        if (e->processed) continue;
        int w = e->to;

        if (!visited[w]) {                     // tree edge
            parent[w] = v;
            e->processed = e->rev->processed = true;
            DFS(w);

            low[v] = min(low[v], low[w]);

            // Insert tree edge into adjacency order
            auto posV = findInsertPos(v, w);   // O(1) via parent info
            auto itV = adjOrder[v].insert(posV, AdjNode{w, nullptr, e->rev, true});
            auto itW = adjOrder[w].insert(adjOrder[w].begin(), AdjNode{v, nullptr, e, true});
            // record for possible rollback
            embedStack.push({v,w,itV,itW,-1});
        }
        else if (dfn[w] < dfn[v] && w != parent[v]) { // back edge upward
            low[v] = min(low[v], dfn[w]);
            e->processed = e->rev->processed = true;

            // Try to insert back edge into current face
            if (!insertBackEdge(v, w)) {
                // Conflict → build separation pair
                SepPair sp = buildSeparationPair(v, w);
                sepStack.push(sp);
                // Re‑enter DFS on the subgraph defined by sp
                processSeparationPair(sp);
                // After subgraph is processed, continue
            }
        }
    }
}

/* insertBackEdge returns true if insertion succeeded,
   false → conflict (needs separation pair handling) */
bool insertBackEdge(int v, int w) {
    // Determine the face where (v,w) should be placed:
    // face = top of embedStack (or a global faceID = 0 for outer face)
    int face = (embedStack.empty() ? 0 : embedStack.top().faceID);

    // Find legal position in v's circular list:
    auto pos = findLegalInsertPos(v, w, face);
    if (pos == adjOrder[v].end()) return false; // no slot → conflict

    auto itV = adjOrder[v].insert(pos, AdjNode{w, nullptr, edgeRev(v,w), true});
    auto itW = adjOrder[w].insert(findLegalInsertPos(w, v, face), AdjNode{v, nullptr, edgeRev(w,v), true});

    embedStack.push({v,w,itV,itW,face});
    return true;
}

/* processSeparationPair recursively handles the subgraph */
void processSeparationPair(const SepPair& sp) {
    // mark vertices in sp.verts as unvisited for a fresh DFS
    for (int v : sp.verts) visited[v] = false;
    // run DFS only on this induced subgraph
    for (int v : sp.verts)
        if (!visited[v]) DFS(v);
    // after finishing, the subgraph is embedded; merge its order
    mergeSubEmbedding(sp);
}