Comparability graphs and intersection graphs |
| |
Authors: | Martin Charles Golumbic Doron Rotem Jorge Urrutia |
| |
Affiliation: | Bell Laboratories, Murray Hill, NJ, USA;University of Waterloo, Waterloo, Ontario, Canada;Universidad Autonoma, Metropolitana-Iztapalapa, Mexico D.F., Mexico |
| |
Abstract: | A function diagram (f-diagram) D consists of the family of curves {ñ} obtained from n continuous functions . We call the intersection graph of D a function graph (f-graph). It is shown that a graph G is an f-graph if and only if its complement ? is a comparability graph. An f-diagram generalizes the notion of a permulation diagram where the fi are linear functions. It is also shown that G is the intersection graph of the concatenation of ?k permutation diagrams if and only if the partial order dimension of . Computational complexity results are obtained for recognizing such graphs. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|