寻求可生成外平面嵌入（outerplanar embedding）的算法及相关文献

存在可以生成外平面嵌入的算法，且可以实现类似NetworkX中check_planarity的功能——判定图是否为外平面图，若为真则返回包含顶点邻边顺时针顺序的嵌入。以下是具体的实现思路、相关文献及可行方案：

一、核心思路 #

外平面图是平面图的子类，其嵌入要求所有顶点位于外部面（无界面）。生成嵌入的核心步骤分为两步：外平面性判定 + 构造符合要求的嵌入。

1. 外平面性判定 #

外平面图的充要条件可用于快速判定：

• 图中不存在与K4（完全图）或K2,3（完全二分图）同胚的子图；
• 等价判定：连通外平面图的顶点数n、边数m满足m ≤ 2n - 3（树的情况m = n-1，符合该不等式）；若为非连通图，每个连通分支需满足此条件。

也可基于经典的平面性判定算法（如Boyer-Myrvold算法）修改：在判定平面性的同时，额外检查是否存在一个包含所有顶点的外部面。

2. 外平面嵌入构造 #

根据图的结构不同，构造方式分为两类：

• 树结构（无环外平面图）：直接为每个顶点的邻边指定任意顺时针顺序即可（树无环，嵌入时不会出现边交叉），也可按顶点编号或层级顺序排列。
• 带环的连通外平面图：
  1. 首先找到外部面的边界序列：该序列是一个包含所有顶点的闭行走（可能由多个环组成，但所有顶点都在边界上）；
  2. 对每个顶点，先按外部面边界的顺时针顺序排列其相邻顶点，再插入内部边的邻接顶点——内部边的两个端点在外部面序列上的位置需满足嵌套关系，以此保证无交叉；
  3. 最终每个顶点的邻边顺序即为符合要求的顺时针嵌入顺序。

二、参考文献 #

若需自行实现，以下文献提供了算法的理论基础和具体步骤：

• 《Planar Graphs: Theory and Algorithms》（Nishizeki, T., & Chiba, N.）：书中专门章节讲解外平面图的判定与嵌入构造，包含可直接落地的算法框架。
• 《Graph Algorithms and Applications》（Di Battista, G., et al.）：在外平面图部分详细阐述了外部面构造、邻边顺序维护的具体逻辑。
• Boyer, J. M., & Myrvold, W. J. (2004). On the cutting edge: Simplified O(n) planarity by edge addition.：经典平面性判定论文，修改后可适配外平面性判定与嵌入生成，时间复杂度为线性O(n)。

三、基于现有工具的快速方案 #

如果不想从头实现，可以基于NetworkX的check_planarity输出调整：

1. 先用check_planarity判定图为平面图，同时获取平面嵌入；
2. 检查嵌入的外部面是否包含所有顶点：若否，通过翻转面（交换外部面与内部面）的操作，将包含所有顶点的面设为外部面；
3. 最后调整每个顶点的邻边顺序，使其符合外部面的顺时针方向要求。

内容的提问来源于stack exchange，提问作者N C