## 1 Introduction  
A graph \(G=(V,E)\) is said to be an intersection graph if and only if there is a set of objects such that each vertex \(v\) in \(V\) corresponds to an object \(O_{v}\) and \(\{u,v\}\in E\) if and only if \(O_{v}\) and \(O_{u}\) have a nonempty intersection. Interval graphs are a typical intersection graph class, and widely investigated. One reason is that interval graphs have wide applications including scheduling and bioinformatics [1]. Another reason is that an interval graph has a simple structure, and hence we can solve many problems efficiently, whereas the problems are hard in general [1,2]. Some natural generalizations and/or restrictions on interval graphs have been investigated (see, e.g., [2, 3, 4]). One of the reasons why these intersection graphs are investigated is that their geometric representations sometimes give intuitive simple proof of the tractable/intractable results. On the tractable results, we can solve a problem by using their geometric representations. The geometric representation of a graph gives us an intuitive expression of how to solve a problem using the representation. On the other hand, on the intractable representation, we can express the difficulty of a problem using the geometric representation of a graph. This gives us an intuition of why the problem is difficult to solve. That is, the property of the graph representation also represents the intractableness of the problem. This extracts the essence of the difficulty of the problem and helps us to understand not only the property of the class of graphs, but also the difficulty of the problem. In this paper, the author reorganizes and shows some related results about graph classes with geometric representations presented at two conferences [5, 6] with recent progress. We will mainly consider threshold graphs, chain graphs, and grid intersection graphs. A threshold graph is a graph such that each vertex has a weight, and two vertices are adjacent if and only if their total weight is greater than a given threshold value. The vertex set of a threshold graph is partitioned into two groups such that \"light\" vertices induce an independent set while \"heavy\" vertices induce a clique. The threshold graphs form a proper subclass of interval graphs, and can be represented in a compact representation of \(O(n)\) space. A chain graph is a bipartite analogy of the notion of threshold graphs. From a threshold graph, we can obtain a chain graph by removing edges between heavy vertices. In a sense, a chain graph can be seen as a two dimensional extension of a threshold graph. From this viewpoint, a grid intersection graph is a two dimensional extension of an interval graph. More precisely, a bipartite graph \(G=(X,Y,E)\) is a grid intersection graph if and only if each vertex \(x\in X\) (and \(y\in Y\)) corresponds to a vertical line (a horizontal line, resp.) such that two vertices are adjacent when they are crossing. We first focus on a tractable problem on a graph that has a geometric representation. The bandwidth problem is one of the classic problems defined below. A layout of a graph \(G=(V,E)\) is a bijection \(\pi\) between the vertices in \(V\) and the set \(\{1,2,\ldots,|V|\}\). The bandwidth of a layout \(\pi\) equals \(\max\{|\pi(u)-\pi(v)|\mid\{u,v\}\in E\}\). The bandwidth of \(G\) is the minimum bandwidth of all layouts of \(G\). The bandwidth has been studied since the 1950s; it has applications in sparse matrix computations (see [7, 8] for survey). From the graph theoretical point of view, the bandwidth of \(G\) is strongly related to the proper interval completion problem [9]. The proper interval completion problem is motivated by research in molecular biology, and hence it attracts much attention (see, e.g., [10]). However, computing the bandwidth of a graph \(G\) is one of the basic and classic \(\mathcal{NP}\)-complete problems [11] (see also [12, GT40]). Especially, it is \(\mathcal{NP}\)-complete even if \(G\) is restricted to a caterpillar with hair length 3 [13].