Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Trapezoid graph
Summary
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 algorithms for chromatic number, weighted independent set, clique cover, and maximum weighted clique.
Given a channel, a pair of two horizontal lines, a trapezoid between these lines is defined by two points on the top and two points on the bottom line. 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.
The interval order dimension of a partially ordered set, , is the minimum number d of interval orders P1 ... Pd such that P = P1∩...∩Pd. The incomparability graph of a partially ordered set is the undirected graph where x is adjacent to y in G if and only if x and y are incomparable in P. An undirected graph is a trapezoid graph if and only if it is the incomparability graph of a partial order having interval order dimension at most 2.
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. This net can be represented by a trapezoid containing the rightmost terminals and leftmost terminals with the same label. Nets may be routed without intersection if and only if the corresponding trapezoids do not intersect. Therefore, the number of layers needed to route the nets without intersection is equal to the graph’s chromatic number.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.