Trapezoid graph
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.
algorithms for chromatic number, weighted independent set, clique cover, and maximum weighted clique.
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.
, is the minimum number d of interval orders P1 … Pd such that P = P1∩…∩Pd.
The incomparability graph of a partially ordered set
[1] The problems of finding maximum cliques and of coloring trapezoid graphs are connected to channel routing problems in VLSI design.
Given some labeled terminals on the upper and lower side of a two-sided channel, terminals with the same label will be connected in a common net.
Therefore, the number of layers needed to route the nets without intersection is equal to the graph’s chromatic number.
Dominating rectangles, or box representation, maps the points on the lower of the two lines of the trapezoid representation as lying on the x-axis and that of the upper line as lying on the y-axis of the Euclidean plane.
Each trapezoid then corresponds to an axis-parallel box in the plane.
Thus, two trapezoids are disjoint exactly if their corresponding boxes are comparable.
The box representation is useful because the associated dominance order allows sweep line algorithms to be used.
An order is a bitolerance order if and only if there are intervals Ix and real numbers t1(x) and tr(x) assigned to each vertex x in such a way that x < y if and only if the overlap of Ix and Iy is less than both tr(x) and t1(y) and the center of Ix is less than the center of Iy.
[4] The class of trapezoid graphs properly contains the union of interval and permutation graphs and is equivalent to the incomparability graphs of partially ordered sets having interval order dimension at most two.
This occurs when both of the trapezoid’s points on the upper channel are in the same position and both points on the lower channel are in the same position.
algorithm for maximum weighted independent set problem and an
algorithm for the maximum weighted clique problem.
They were first proposed by Felsner, and they rely on the definition of dominating boxes carrying over to higher dimensions in which a point x is represented by a vector
Using (k − 1)-dimensional range trees to store and query coordinates, Felsner’s algorithms for chromatic number, maximum clique, and maximum independent set can be applied to k-trapezoid graphs in
For this larger class of graphs, the maximum independent set and the minimum clique cover problem can be solved in
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
algorithms for chromatic number, weighted independent set, clique cover, and maximum weighted clique.
Felsner proposes using balanced trees that can do insert, delete, and query operations in
is a trapezoid graph, search for a transitive orientation
The fastest algorithm for trapezoid order recognition was proposed by McConnell and Spinrad in 1994, with a running time of
[6] Using vertex splitting, the recognition problem for trapezoid graphs was shown by Mertzios and Corneil to succeed in
This process involves augmenting a given graph
, and then transforming the augmented graph by replacing each of the original graph’s vertices by a pair of new vertices.
