Tractabilities and Intractabilities on Geometric Intersection Graphs *

Algorithms

关键词: bandwidth;    chain graphs;    graph isomorphism;    Hamiltonian path problem;    interval graphs;    threshold graphs;    unit grid intersection graphs;   

DOI  :  10.3390/a6010060

来源: mdpi

【 摘 要 】

A graph is said to be an intersection graph if there is a set of objects such that each vertex corresponds to an object and two vertices are adjacent if and only if the corresponding objects have a nonempty intersection. There are several natural graph classes that have geometric intersection representations. The geometric representations sometimes help to prove tractability/intractability of problems on graph classes. In this paper, we show some results proved by using geometric representations.

【 授权许可】

CC BY   
© 2013 by the authors; licensee MDPI, Basel, Switzerland.