%0 Journal Article
%T Tractabilities and Intractabilities on Geometric Intersection Graphs
%A Ryuhei Uehara
%J Algorithms
%D 2013
%I MDPI AG
%R 10.3390/a6010060
%X 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.
%K bandwidth
%K chain graphs
%K graph isomorphism
%K Hamiltonian path problem
%K interval graphs
%K threshold graphs
%K unit grid intersection graphs
%U http://www.mdpi.com/1999-4893/6/1/60