Trapezoid graph

In graph theory, trapezoid graphs are intersection graphs of trapezoids between two horizontal lines. They are a class of co-comparability graphs that contain interval graphs and permutation graphs as subclasses. A graph is a trapezoid graph if there exists a set of trapezoids corresponding to the vertices of the graph such that two vertices are joined by an edge if and only if the corresponding trapezoids intersect. Trapezoid graphs were introduced by Dagan, Golumbic, and Pinter in 1988.There exists ${O}(n\log n)$ algorithms for chromatic number, weighted independent set, clique cover, and maximum weighted clique.

Figure 2: Trapezoid representation of graph G.

Algorithms

Algorithms for trapezoid graphs should be compared with algorithms for general co-comparability graphs. For this larger class of graphs, the maximum independent set and the minimum clique cover problem can be solved in ${O}(n^{2}\log n)$ time. Dagan et al. first proposed an ${O}(nk)$ algorithm for coloring trapezoid graphs, where n is the number of nodes and k is the chromatic number of the graph. Later, using the box representation of trapezoid graphs, Felsner published ${O}(n\log n)$ algorithms for chromatic number, weighted independent set, clique cover, and maximum weighted clique. These algorithms all require ${O}(n)$ space. These algorithms rely on the associated dominance in the box representation that allows sweeping line algorithms to be used. Felsner proposes using balanced trees that can do insert, delete, and query operations in ${O}(\log n)$ time, which results in ${O}(n\log n)$ algorithms.

Recognition

To determine if a graph ${G}$ is a trapezoid graph, search for a transitive orientation ${F}$ on the complement of ${G}$. Since trapezoid graphs are a subset of co-comparability graphs, if ${G}$ is a trapezoid graph, its complement ${G'}$ must be a comparability graph. If a transitive orientation ${F}$ of the complement ${G'}$ does not exist, ${G}$ is not a trapezoid graph. If ${F}$ does exist, test to see if the order given by ${F}$ is a trapezoid order. The fastest algorithm for trapezoid order recognition was proposed by McConnell and Spinrad in 1994, with a running time of $O(n^{2})$. The process reduces the interval dimension 2 question to a problem of covering an associated bipartite graph by chain graphs (graphs with no induced 2K₂). Using vertex splitting, the recognition problem for trapezoid graphs was shown by Mertzios and Corneil to succeed in $O(n(n+m))$ time, where $m$ denotes the number of edges. This process involves augmenting a given graph ${G}$, and then transforming the augmented graph by replacing each of the original graph’s vertices by a pair of new vertices. This “splitted graph” is a permutation graph with special properties if an only if ${G}$ is a trapezoid graph.

References

• Golumbic, Martin Charles (1980). "Algorithmic Graph Theory and Perfect Graphs" (Document). Academic Press. ISBN 0-444-51530-5. {{cite document}}: Invalid |ref=harv (help); Unknown parameter |url= ignored (help) Second edition, Annals of Discrete Mathematics 57, Elsevier, 2004.