边缘类型异常的平面度测试
Planarity Testing with exceptions for edge types
我想了解是否可以增强平面性检查算法（例如 LR 平面性、PC 树、PQ 树等...），以便允许某些边缘根据其类型交叉。
我有一个包含 3 种不同类型边的图：A、B、C
类型 A 的边不能与任何其他边相交。
类型 B 的边可以交叉类型 C 的边，反之亦然。
我已经看过一个简单的 LR 平面度测试，但无法成功实现此功能。
是否可以采用现有算法并使用这些规则对其进行调整，或者是否已经有支持该算法的算法？
取只包含A类边的子图，用标准的平面度测试算法看它是否是平面的。
注意：一张图可能 generate multiple planar embeddings [第 60 页]，因此您可能需要考虑这一点。
一旦你有了 A 类边的平面嵌入，你就可以生成一个面列表。
从A类边生成的平面子图中的两个顶点连接的B类边路径只能以平面方式绘制（不交叉任何A类边）如果端点路径都在嵌入的单个面的边界上。根据约旦曲线定理，将其添加到嵌入中将平分执行嵌入的面并生成两个子面。
注意：同样，一条路径可能能够平分多个面，因此您可能有多个潜在的嵌入。
继续执行类型 B edges/paths 的嵌入，它在两端连接到类型 A 子图，并且在每一步平分一个面，直到你到达没有可行的面可平分的点（并且图形是非平面的）或者类型 A 和类型 B 的边是平面的。
由于 C 类边可以与 B 类边交叉（反之亦然），您可以将 C 类边（使用相同的面二分法）嵌入到 A 类子图中而不考虑 B 类边（因为它们可以交叉）。
虽然对于类型 A 和 B 或 C（因为这实际上只是一个普通的平面嵌入），这可以在 O(N) 中完成，但您可能必须测试多个嵌入以找到面部的方向同时适用于 A、B 和 C，生成的算法几乎肯定不会是 O(N)。
或者，如果您知道在生成不同的嵌入时对面部排列的约束，那么添加某种基于约束的求解器来协调嵌入中路径的方向可能会有所帮助。
在不进行平面性测试的情况下，取具有B类和C类边的子图，然后通过平面性测试算法尝试将A类边添加到子图中。
我想了解是否可以增强平面性检查算法（例如 LR 平面性、PC 树、PQ 树等...），以便允许某些边缘根据其类型交叉。
我有一个包含 3 种不同类型边的图：A、B、C
类型 A 的边不能与任何其他边相交。
类型 B 的边可以交叉类型 C 的边，反之亦然。
我已经看过一个简单的 LR 平面度测试，但无法成功实现此功能。
是否可以采用现有算法并使用这些规则对其进行调整，或者是否已经有支持该算法的算法？
取只包含A类边的子图，用标准的平面度测试算法看它是否是平面的。
注意：一张图可能 generate multiple planar embeddings [第 60 页]，因此您可能需要考虑这一点。
一旦你有了 A 类边的平面嵌入，你就可以生成一个面列表。
从A类边生成的平面子图中的两个顶点连接的B类边路径只能以平面方式绘制（不交叉任何A类边）如果端点路径都在嵌入的单个面的边界上。根据约旦曲线定理，将其添加到嵌入中将平分执行嵌入的面并生成两个子面。
注意：同样，一条路径可能能够平分多个面，因此您可能有多个潜在的嵌入。
继续执行类型 B edges/paths 的嵌入，它在两端连接到类型 A 子图，并且在每一步平分一个面，直到你到达没有可行的面可平分的点（并且图形是非平面的）或者类型 A 和类型 B 的边是平面的。
由于 C 类边可以与 B 类边交叉（反之亦然），您可以将 C 类边（使用相同的面二分法）嵌入到 A 类子图中而不考虑 B 类边（因为它们可以交叉）。
虽然对于类型 A 和 B 或 C（因为这实际上只是一个普通的平面嵌入），这可以在 O(N) 中完成，但您可能必须测试多个嵌入以找到面部的方向同时适用于 A、B 和 C，生成的算法几乎肯定不会是 O(N)。
或者，如果您知道在生成不同的嵌入时对面部排列的约束，那么添加某种基于约束的求解器来协调嵌入中路径的方向可能会有所帮助。
在不进行平面性测试的情况下，取具有B类和C类边的子图，然后通过平面性测试算法尝试将A类边添加到子图中。