平面性測試，除了邊緣類型的例外

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型邊添加到子圖中。