Tractabilities and Intractabilities on Geometric Intersection Graphs

Abstract

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.

Keywords

• bandwidth
• chain graphs
• graph isomorphism
• Hamiltonian path problem
• interval graphs
• threshold graphs
• unit grid intersection graphs