Circular and Circle Trapezoid Graphs
Yaw-Ling Lin · 2006
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(n 2 loglog n) time; whereas, the minimum weighted independent dominating set of circular trapezoid graphs can be found in O(n 2 log n) time.