algorithm - 边缘类型异常的平面度测试

Question

我想了解是否可以增强平面性检查算法(例如 LR 平面性、PC 树、PQ 树等...)，以便允许某些边根据其类型交叉。

我有一个包含 3 种不同类型边的图:A、B、C

类型 A 的边不能与任何其他边交叉。

类型 B 的边可以与类型 C 的边交叉，反之亦然。

我已经看过一个简单的 LR 平面度测试，但无法成功实现此功能。

是否可以采用现有算法并根据这些规则对其进行调整，或者是否已经有支持该算法的算法？

Answer 1

取仅包含类型 A 边的子图，并使用标准的平面性测试算法来查看它是否是平面的。

注意:一张图可能 generate multiple planar embeddings [第 60 页]，因此您可能需要考虑这一点。

一旦你有了 A 类边的平面嵌入，你就可以生成一个面列表。

从 A 类边生成的平面子图中的两个顶点连接的 B 类边路径只能以平面方式绘制(不交叉任何 A 类边)如果路径的端点都在嵌入的单个面的边界上。根据 Jordan 曲线定理，将其添加到嵌入中将平分执行嵌入的面并生成两个子面。

注意:同样，一条路径可能能够平分多个面，因此您可能有多个潜在的嵌入。

继续执行 B 型边缘/路径的嵌入，其两端连接到 A 型子图，并且在每一步平分一个面，直到您到达没有可行的面可平分的点(和图是非平面的)或类型 A 和类型 B 边缘是平面的。

由于 C 类边可以与 B 类边交叉(反之亦然)，您可以将 C 类边(使用相同的面二分法)嵌入到 A 类子图中，而无需考虑 B 类边(因为它们可以被交叉)。

虽然这可以在 O(N) 中为类型 A 和 B 或 C 完成(因为这实际上只是一个普通的平面嵌入)，您可能必须测试多个嵌入以找到适用于A、B 和 C 加在一起，生成的算法几乎肯定不会是 O(N)。

或者，如果您知道生成不同嵌入时人脸排列的​​约束，那么添加某种基于约束的求解器来协调嵌入中路径的方向可能会有所帮助。