WikiEdge:ArXiv-2409.01889v1/summary

編輯

本文研究了平面圖的弱分層平面圖，其中每個頂點表示為沿水平線序列（稱為層級）的點，每條邊要麼是水平線段，要麼是嚴格單調的曲線。如果一個圖允許這樣的繪製，其中邊的跨度至多為s，則稱該圖為s-跨度弱分層平面圖。我們從計算和組合的角度探討了計算s-跨度弱分層平面圖的問題。我們證明了這個問題相對於其自然參數s是para-NP難的，並研究了其相對於廣泛使用的結構參數的複雜性。我們展示了關於頂點覆蓋數的多項式大小的核的存在，並證明了當以樹深度為參數時，該問題是FPT。我們還為各種圖類提供了跨度的上下界。值得注意的是，我們展示了循環樹，一種2-外平面圖的家族，概括了Halin圖，是Θ(log n)-跨度弱分層平面圖，並且當3-連通時是4-跨度弱分層平面圖。作為這些組合結果的副產品，我們得到了所考慮的圖族的邊長比的改進界限。