圓形梯形圖與循環梯形圖

Circular and Circle Trapezoid Graphs

過去，在圖形演算法的研究中，曾經將interval graphs 與permutation graphs 推廣到梯形圖（trapezoid graphs）上，並且在許多梯形圖上的最佳化問題演算法的研究中獲得許多重要的成果。最近這幾年的研究漸漸將梯形圖導引推廣到更一般層次的方向。令圓形梯形表示一個連結同一圓中二弦之區域；那麼圓形梯形圖（circle trapezoid graphs）則為由這些圓形梯形之重疊關係所定義之圖形。令循環梯形表示介於二個同心圓內二平行圓弧之間的區域；那麼循環梯形圖（circular trapezoid graphs）則為由這些循環梯形之重疊關係所定義之圖形。不難驗證，梯形圖與circular-arc graphs 同為圓形梯形圖與循環梯形圖之子集合。 在本文裡，作者提出關於圓形梯形圖與循環梯形圖之部分研究成果。我們發現循環梯形圖與圓形梯形圖分別隸屬於不同集合。最佳化問題演算法上，我們提出O(n2loglog n) 時間演算法在循環梯形圖上尋找最大權重獨立點集合；我們並提出O(n2log n) 時間演算法在圓形梯形圖上尋找最小權重獨立控制點集合。 Along with the direction that generalizes interval graphs and permutation graphs to trapezoid graphs, researchers are now trying to generalize the class known as trapezoid graphs. A circle trapezoid is the region in a circle that lies between two non-crossing chords; thus, circle trapezoid graphs are the intersecting graphs of circle trapezoids within a circle. It should be noted that circle trapezoid graphs properly contain trapezoid graphs, circle graphs and circular-arc graphs as subclasses. Circle trapezoid graphs should not be confused with circular trapezoid graphs. A circular trapezoid is the region within two parallel circles that lies between two non-crossing segments; circular trapezoid graphs are the intersecting graphs of circular trapezoids between two parallel circles. In this paper, the author presents results on two proper super classes of trapezoid graphs, including circle trapezoid graphs and circular trapezoid graphs. It is shown that circle trapezoid graphs and circular trapezoid graphs are two distinct classes of graphs. Furthermore, it is shown that the maximum weighted independent set on circular trapezoid graphs can be found in O(n2loglog n) time; whereas, the minimum weighted independent dominating set of circular trapezoid graphs can be found in O(n2log n) time.