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

fangzichang · 2025-08-13 19:21:29 · 算法·理论

完全使用 gpt-oss-120b 生成。

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

作者：John Boyer、Robert Myrvold（2004）
核心思想：在一次深度优先搜索（DFS）过程中维护 嵌入信息，并在发现冲突时即时“回滚”或“恢复”。该实现比 1974 年的 Hopcroft‑Tarjan 版更简洁、常数因子更小，已成为多数平面性检测库（如 Boost、NetworkX、Planarity）默认的内部实现。

下面从 概念 → 数据结构 → 主要步骤 → 细节实现 → 时间/空间复杂度 → 实用要点 逐层展开。

1. 基本概念

目标：在 O(|V|) 时间内判断图是否平面，并在平面情况下输出 每个顶点的环序（即组合嵌入）。几何坐标（直线嵌入）可以随后通过 Tutte、FPP 等方法从环序转化。

2. 关键数据结构

实现技巧：

• 使用 邻接表 + 边对象，每条边保存两个方向的 EdgeInfo（包括指向对方的 rev、在对应顶点的迭代器位置）。
• EdgeInfo 里额外保存 bool processed 标记，防止同一 back edge 被多次插入。
• adjacency order 用 circular doubly linked list，因为插入时需要在 O(1) 时间把新边放在两已有邻居之间。

3. 算法的主要步骤

3.1 初始化

1. dfn = 0，所有 low = ∞，parent = -1。
2. 对每个未访问的顶点 v 调用 DFS(v)（处理非连通图的情况）。

3.2 深度优先搜索（DFS） + 嵌入维护

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)

核心子过程：

1. InsertTreeEdgeIntoAdjOrder(v, w)

   • 在 v 的环序中把 w 插入 父子位置（即在 v 的当前面中把 w 放在 v 与其父的相邻位置之间）。
   • 同时在 w 的环序中把 v 插入对应位置（形成互补的环）。

2. InsertBackEdgeIntoAdjOrder(v, w)

   • 需要 确定 back edge 所在的 面（即当前 DFS 栈中最近的未闭合面）。
   • 使用 嵌入栈 S：每当进入一个 back edge时，把 (v,w,faceID) 入栈；当后续的树边或 back edge导致该面闭合时弹出。
   • 插入时把 w 放在 v 的 环序中与 v 的父/子邻居之间的 正确位置（由栈顶的 faceID 决定）。

3. 冲突检测 & 分离对处理

   • 当尝试把 back edge 插入时，如果在 v 的环序中找不到合法的插入位置（即两相邻的已插入边已经占用了所有可用槽），则产生 冲突。
   • 冲突必然表现为 两个相邻的 back edge 交叉形成 separation pair。
   • 处理方式：把冲突的子图压入分离对栈，递归地在该子图内部重新执行 DFS（相当于把原图拆成若干子块），每块独立检测平面性。
   • 关键是 “回滚”：弹出嵌入栈 S 中对应的插入操作，恢复到冲突前的环序状态，然后在子图内部重新构造。

3.3 完成 DFS 后的收尾

• 当所有顶点都被遍历完，且 没有出现不可回滚的冲突，则 embedding（即每个顶点的环序）即为 合法的组合平面嵌入。
• 若在任意一步出现 不可回滚的冲突（即冲突的两个 back edge不在同一面，且无法通过分离对拆分），则报告 非平面。

4. 细节实现要点

4.1 环序的维护（双向循环链表）

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

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

• 插入：adjOrder[v].insert(pos, node)，其中 pos 是通过 findInsertPosition(v, w) 获得的迭代器。
• 删除（回滚时）：adjOrder[v].erase(node.it)。

4.2 嵌入栈的结构

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

stack<EmbedOp> embedStack;

• Push：在 InsertBackEdgeIntoAdjOrder 时记录。
• Pop：在冲突回滚时弹出并使用 uPos/vPos 删除对应的邻接记录。

4.3 分离对的递归处理

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

stack<SepPair> sepStack;

• 当冲突出现时，构造子图：取冲突两条 back edge 所围成的顶点集合（可通过 DFS 在当前栈中标记），压入 sepStack。
• 递归调用 DFS 只在该子图上进行，使用 局部的 dfn/low（保持全局编号不变，只在子图内部重新计算）。
• 子图处理完毕后，合并：把子图的环序嵌入直接拼回到全局 adjOrder 中（因为子图本身已经是平面的）。

4.4 复杂度控制

• 每条边最多被处理两次（一次作为 tree edge，一次作为 back edge）。
• 每次插入/删除操作均 O(1)（链表操作）。
• 冲突回滚 只涉及弹出栈中对应的操作，整体仍线性。
• 分离对递归：每次递归处理的子图大小严格小于原图，且每条冲突只会产生一次递归。
• 因此 总时间 O(|V| + |E|) = O(n)，空间 O(n)（DFS 栈 + 嵌入栈）。

5. 伪代码完整示例（C++‑风格）

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);
}

说明

• findInsertPos / findLegalInsertPos 通过父指针或已有 faceID 快速定位（常数时间）。
• edgeRev(u,v) 返回指向相反方向的 Edge*，用于同步两端的 processed 标记。
• buildSeparationPair 通过在当前 DFS 栈中寻找两条相邻的 back edge，收集它们围住的顶点集合（可用 BFS/DFS 标记）。
• mergeSubEmbedding 把子图的 adjOrder 合并到全局结构，保持环序的一致性。

6. 正确性要点（为什么是线性）

1. DFS 树的 lowpoint 规则保证每条 back edge只能指向祖先，避免出现向后跨越多层的情况。
2. 嵌入栈记录所有插入操作，使得冲突时只需弹出最近的若干操作，不需要重新遍历已完成的子树。
3. 分离对递归把冲突局部化为子图，子图大小严格递减，且每条冲突只会产生一次递归。
4. 每条边最多一次插入（无论是 tree 还是 back），且每次插入/删除都是 O(1)。
5. DFS 本身线性，加上上述常数时间的嵌入维护，整体 O(n)。

7. 从组合嵌入到几何嵌入

完成 Boyer‑Myrvold 后，你会得到 每个顶点的邻接环序（即 adjOrder[v] 的循环顺序）。要把它转化为实际坐标，可任选以下方法：

实现建议：如果你使用 Python + NetworkX，nx.check_planarity(G, counterexample=False) 已经返回 PlanarEmbedding（即环序），随后可以直接调用 nx.combinatorial_embedding_to_pos(embedding)（或自行实现 Tutte）得到几何坐标。

8. 实际实现参考

调试技巧

• 在实现时加入 断言：每次 insertBackEdge 前检查 adjOrder[v] 中是否已经出现 w，防止重复插入。
• 使用 可视化（如在每次插入后绘制当前环序）帮助定位冲突产生的具体位置。
• 对于大规模图（>10⁶ 边），建议使用 稀疏矩阵 +并行化 的 lowpoint 计算（虽然理论上 O(n) 已足够快），但实际 I/O 成本往往是瓶颈。

9. 小结

只要在 DFS 过程中严格维护 嵌入栈 与 环序链表，并在冲突时通过 分离对递归 处理子图，Boyer‑Myrvold 就能在 线性时间 完成平面性检测并输出完整的平面嵌入。祝你实现顺利！如果还有具体实现细节或代码调试上的疑问，欢迎继续交流。