Trapezoid graph

Uses your system voice; voice and rate in settings.

Snapshot

≈ 2 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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.

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.

Notes

References

Second edition, Annals of Discrete Mathematics 57, Elsevier, 2004.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1377108386 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001377108386 · captured 1790542749.0 · version history

Cite this page as: encyclopegia.org, “Trapezoid graph”, snapshot enwiki-001377108386. https://encyclopegia.org/a/trapezoid-graph

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.