平面性测试，除了边缘类型的例外

Question

我想了解平面性检查算法（如LR Planarity，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型（反之亦然），所以可以在不考虑B型边缘的情况下将类型C边缘（使用相同的二等分方法）嵌入到A型子图中（因为它们可以交叉）。

虽然这可以在O（N）中对A型和B或C（因为这实际上只是一个普通的平面嵌入）完成，您可能必须测试多个嵌入以找到工作面的方向对于A，B & C，所得到的算法几乎肯定不会是O（N）。

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

Answer 2

将带有B型和C型边的子图应用平面度测试，然后尝试使用平面度测试算法将A型边添加到子图中。