有向图的平面性检测（基于嵌入的平面性测试）

题目描述
给定一个有向图 G=(V, E)，要求判断 G 是否可以画在平面上，使得其边之间除了在端点处外没有交叉，同时每条边都按照其方向（从尾部指向头部）以单调（通常为直线或曲线）的方式绘制。这被称为有向平面图（digraph planarity）的判断问题。注意，这里的有向性不改变平面性的几何约束，但某些算法在考虑有向性时可能有更严格的嵌入要求（例如避免边交叉的同时保持方向可辨识）。本问题聚焦于基于嵌入的平面性测试，即尝试构建一个平面嵌入（planar embedding）来证明其平面性，而非仅通过Kuratowski定理等禁用子图判定。

解题步骤

1. 问题转化

   • 有向图的平面性等价于忽略边方向后所得无向图的平面性。因为有向性只附加方向信息，不影响边能否不相交地画在平面上。
   • 因此，我们先将有向图 G 转化为无向图 G'：保留所有顶点，每条有向边转化为无向边（若有多条平行边，保留一条即可，因平面性不考虑边方向时多重边不影响结果，但实际中需处理多重边情形）。
   • 目标转化为：判断无向图 G' 是否为平面图，若是，则原 G 有向平面图。

2. 平面性测试的基本概念

   • 平面图满足欧拉公式：对连通图，V - E + F = 2，其中 F 是面数。
   • 平面图必要条件：若 V ≥ 3，则 E ≤ 3V - 6（简单图）；若图无三角形，则 E ≤ 2V - 4。
   • 但必要非充分，需用平面性算法判定。
   • 常用算法：Boyter-Myrvold 平面性测试（基于深度优先搜索的嵌入构建），或经典 Hopcroft-Tarjan 线性时间算法。这里以增量嵌入法（通常用于教学）为例讲解。

3. 算法核心：增量嵌入法

   • 基本思想：逐条边添加，尝试嵌入当前子图，若无法嵌入新边而不交叉，则图非平面。
   • 步骤：
     a. 选择一个生成树 T 作为初始嵌入（树总是平面的，可画在平面上无边交叉）。
     b. 将非树边（回边）按某种顺序加入。每加一条边 e=(u,v)，检查当前嵌入中是否存在一个面同时包含 u 和 v 在其边界上。
     c. 若存在，则将 e 画在该面内，分割该面为两个新面。
     d. 若不存在，则尝试调整嵌入（通过重新排列某些子图的嵌入），若所有调整失败则图非平面。

4. 详细步骤与例子

   • 假设有一个简单有向图（转化为无向图 G'），顶点集 {1,2,3,4,5}，边集： (1,2),(2,3),(3,4),(4,5),(5,1),(1,3)（无向化后）。
   • 步骤 1：选生成树，比如 T = {(1,2),(2,3),(3,4),(4,5)}，画在平面上形成一条链。
   • 步骤 2：加回边 (5,1)：当前嵌入为一条折线，两端点为 1 和 5，但 1 和 5 不在同一个面边界（只有外面一个面，其边界为整个树，包含 1 和 5，所以可加）。加入后形成一个环，面数增加。
   • 步骤 3：加回边 (1,3)：检查 1 和 3 是否在同一面边界。当前嵌入有两个面：一个内面边界为 1-2-3-4-5-1，一个外面边界相同但方向相反。顶点 1 和 3 同时在两个面边界上，所以可选一面加入 (1,3)。加入后分割面。
   • 步骤 4：若还有边，继续。所有边加入成功，则图平面。

5. 有向性的额外处理

   • 在有向图中，平面嵌入需考虑绘制美观性，如尽量使边方向一致（如从上到下、从左到右），但这不属于平面性判定必须，属于“向上平面图”等变体。
   • 对于本问题，只要无向图平面，原图即为有向平面图。但若要求绘制时避免边交叉且方向不重叠，有时需检测“平面有向图”是否允许所有边同向面边界（如 st-平面图），这是更高级主题，本题不涉及。

6. 算法复杂度与实现提示

   • 增量法最坏 O(|V|²)，但实际常用 Boyter-Myrvold 算法（线性时间 O(|V|)）。
   • 实现时需维护面的边界表示（如双向边表），及支持“遍历面边界”操作。
   • 非平面时，可输出 Kuratowski 子图（K5 或 K3,3 细分）作为证据。

总结
有向图的平面性检测本质是先忽略方向，用无向平面性算法判定。若平面，则存在至少一种嵌入可使有向边无交叉绘制。本题通过增量嵌入法展示了逐步构建嵌入的过程，是理解平面性算法的基础。