## 2 Preliminaries  
The _neighborhood_ of a vertex \(v\) in a graph \(G=(V,E)\) is the set \(N_{G}(v)=\{u\in V\mid\{u,v\}\in E\}\), and the _degree_ of a vertex \(v\) is \(|N_{G}(v)|\) denoted by \(d_{G}(v)\). If no confusion can arise we will omit the index \(G\). For a subset \(U\) of \(V\), the subgraph of \(G\) induced by \(U\) is denoted by \(G[U]\). Given a graph \(G=(V,E)\), its _complement_\(\bar{G}=(V,\bar{E})\) is defined by \(\bar{E}=\{\{u,v\}\mid\{u,v\}\
ot\in E\}\). A vertex set \(I\) is an _independent set_ if and only if \(G[I]\) contains no edges, and then the graph \(\bar{G}[I]\) is said to be a _clique_. Two vertices \(u\) and \(v\) are called _twins_ if and only if \(N(u)\cup\{u\}=N(v)\cup\{v\}\). For a graph \(G=(V,E)\), a sequence of distinct vertices \(v_{0},v_{1},\ldots,v_{l}\) is a _path_, denoted by \((v_{0},v_{1},\ldots,v_{l})\), if \(\{v_{j},v_{j+1}\}\in E\) for each \(0\leq j<l\). The _length_ of a path is the number of edges on the path. For two vertices \(u\) and \(v\), the _distance_ of the vertices, denoted by \(dist(u,v)\), is the minimum length of the paths joining \(u\) and \(v\). A _cycle_ consists of a path \((v_{0},v_{1},\ldots,v_{l})\) of length at least 2 with an edge \(\{v_{0},v_{l}\}\), and is denoted by \((v_{0},v_{1},\ldots,v_{l},v_{0})\). The _length_ of a cycle is the number of edges on the cycle (equal to the number of vertices). A path \(P\) in \(G\) is said to be _Hamiltonian_ if \(P\) visits every vertex in \(G\) exactly once. The _Hamiltonian path problem_ is to determine if a given graph has a Hamiltonian path. The _Hamiltonian cycle problem_ is defined similarly for a cycle. The problems are well known \(\mathcal{NP}\)-complete problem (see, e.g., [12]). An edge that joins two vertices of a cycle but is not itself an edge of the cycle is a _chord_ of that cycle. A graph is _chordal_ if every cycle of length at least 4 has a chord. In this paper, we will discuss about intersection graphs of geometrical objects. Interval graphs are characterized by intersection graphs of intervals, and it is well known that chordal graphs are intersection graphs of subtrees of a tree (see, e.g., [2]). A graph \(G=(V,E)\) is _bipartite_ if and only if \(V\) can be partitioned into two sets \(X\) and \(Y\) such that every edge joins a vertex in \(X\) and the other vertex in \(Y\). We sometimes denote a bipartite graph by \(G=(X,Y,E)\) to specify the two vertex sets. A bipartite graph is _chordal bipartite_ if every cycle of length at least 6 has a chord. A graph \((V,E)\) with \(V=\{v_{1},v_{2},\ldots,v_{n}\}\) is an _interval graph_ if there is a finite set of intervals \(\mathcal{I}=\{I_{v_{1}},I_{v_{2}},\ldots,I_{v_{n}}\}\) on the real line such that \(\{v_{i},v_{j}\}\in E\) if and only if \(I_{v_{i}}\cap I_{v_{j}}\
eq\emptyset\) for each \(i\) and \(j\) with \(0<i,j\leq n\). We call the set \(\mathcal{I}\) of intervals an _interval representation_ of the graph. For each interval \(I\), we denote by \(R(I)\) and \(L(I)\) the right and left endpoints of the interval, respectively (therefore we have \(L(I)\leq R(I)\) and \(I=[L(I),R(I)]\)). An interval representation is called _proper_ if and only if \(L(I)\leq L(J)\) and \(R(I)\leq R(J)\) for every pair of intervals \(I\) and \(J\) or vice versa. An interval graph is _proper_ if and only if it has a proper interval representation. It is known that the class of proper interval graphs coincides with the class of unit interval graphs [43]. That is, any proper interval graph has a proper interval representation that consists of intervals of unit length (explicit and simple construction is given in [44]).