planar-graph

1熱度

1回答

Q.爲什麼凸多邊形被認爲是設計圖形算法的更好選擇？我A.凸多邊形是平面的，更容易夾。我的回答是一種簡短，我不知道如果我的回答是正確的，可誰都擴大或給我一個更好的答案對於這個問題嗎？

3熱度

4回答

我有一組不相交的線，其中一些連接在頂點。我試圖找到包含給定點的最小多邊形（如果存在的話）。所以，在下面的圖片中，在所有線段的列表中，給出紅色的點，我只想得到藍色的點。我正在使用Python，但可能會適應其他語言的算法;我不知道這個問題叫什麼。

2熱度

2回答

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

我想了解平面性檢查算法（如LR Planarity，PC樹，PQ樹等）是否可以增強，使得一些邊緣被允許交叉取決於他們的類型。我有3種不同類型的邊的圖：A，B，C類型A的邊緣不能跨越任何其它邊緣。 B型的邊緣可以與C型的邊緣交叉，反之亦然。我已經看過簡單的LR平面度測試，但無法成功實現此功能。是否有可能採取現有的算法並用這些規則進行調整，或者是否已有算法支持？

4熱度

1回答

如何驗證平面嵌入？

我即將實現一種計算平面嵌入的算法。我已經開始通過針對一組圖表（rome graphs）運行並將我的結果與另一個實現（yfiles）的結果進行比較來驗證我的結果。但是，我只能檢查平面/非平面答案是否相等，因爲對於給定的平面圖可能存在許多不同的嵌入。如何驗證我計算的嵌入（鄰接列表中的排序）是否是正確的平面嵌入？我已經發現了一些可能出現錯誤嵌入的情況。對於失敗的圖通常手動繪製嵌入變得困難。我發現b

0熱度

1回答

關於MST的一些問題

我現在正在學習最小生成樹的主題，並且我理解它的大部分內容，但是我仍然有一些我不明白的東西。我正在處理無向加權圖。首先，我知道找到MST花費O（E * log V）。現在，當我們處理平面圖時，我想優化它到線性時間 - O（V + E）。其次，我看到了單位平方中有n個點的例子，並且我成功地證明了存在權重爲O（sqrt n）的MST。問題是我找不到找到這個MST的算法。感謝所有，或者

8熱度

2回答

最小化在二部圖口岸的數量

下面的算法問題發生在我身上，同時繪製圖形的東西無關：我們有一個二分圖的平面圖紙，與設置在獨立集合如圖所示。我們如何重新排列每列中的節點，以便邊緣交叉點的數量最小化？我知道這個問題對於普通圖（link）是NP-hard，但考慮到圖是雙方的，有一些技巧嗎？作爲後續，如果有什麼是第三列瓦特，其中只有邊緣v？還是進一步？

5熱度

1回答

連接偶數個無節點的節點

我有兩組n個節點。現在我想將一個集合中的每個節點與另一個集合中的另一個節點連接起來。結果圖應該沒有交點。我知道的幾種掃描線算法（Bentley-Ottmann-Algorithm以檢查交叉口發生，但我無法找到一個算法來解決這些路口，除了蠻力的方法。從一組每個節點都可以被連接到任何其它節點的另一組內任何指針（一種有效的）算法，解決了這個問題沒有所需的實施 EDIT1：？這裏是一個解決問題的方

2熱度

1回答

在代碼中表示結嗎？

所以我最近一直在閱讀一些關於圖論和結理論關係的文章，這讓我想到代碼中的結點。我目前對此問題的直覺是將結視爲本質上的平面圖，其中每個頂點位於任何交叉點處。然後，我們還會存儲交叉如何針對任何給定的頂點。這是多麼的完成，或者有更好的方法嗎？謝謝！

2熱度

1回答

用於Boyer-Myrvold平面度測試或Kuratowski子圖識別的Python庫

我正在使用Python中的NetworkX圖形，我想找到任何給定圖形的Kuratowski子圖。 Boyer-Myrvold平面圖測試算法可以返回現有的Kuratowski子圖，如果圖不是平面的（頂點數n中的O（n）），所以我希望可能已經有一個實現算法或Python中的類似算法。我一直無法找到一個，而我稍微不願意從原始研究報告中重新實施它。如果它可以輕鬆地與NetworkX庫進行圖形接口，那更好

1熱度

1回答

繪製平面圖的算法

如果我有他的面孔列表，是否有繪製平面圖的算法？我知道有一些複雜的算法，如路徑添加和頂點添加，它測試平面性和產生平面嵌入，但它不是我正在尋找。