algorithm - 平面性测试，边缘类型除外

Question

我试图了解是否可以增强平面性检查算法（例如 LR Planarity、PC 树、PQ 树等），以便允许某些边缘根据其类型交叉。

我有一个带有 3 种不同类型边的图：A、B、C

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

B 型边可以穿过 C 型边，反之亦然。

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

是否可以采用现有算法并使用这些规则对其进行调整，或者是否已经有一种算法支持这一点？

Answer 1

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

注意：一个图可能会生成多个平面嵌入​​[第 60 页]，因此您可能需要考虑这一点。

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

从 A 类边生成的平面子图中的两个顶点连接的 B 类边路径只有在路径的端点都在嵌入的单个面的边界。根据 Jordan 曲线定理，将其添加到嵌入中将平分执行嵌入的面并生成两个子面。

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

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

由于 C 型边可以穿过 B 型（反之亦然），您可以将 C 型边（使用相同的面二等分方法）嵌入到 A 型子图中，而无需考虑 B 型边（因为它们可以交叉） .

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

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

Answer 2

在不应用平面性测试的情况下获取具有 B 类和 C 类边的子图，然后尝试通过应用平面性测试算法将 A 类边添加到子图中。