REALIZING INTERVAL-GRAPHS WITH SIZE AND DISTANCE CONSTRAINTS

We study the following problem: given an interval graph, does it have a realization which satisfies additional constraints on the distances between interval endpoints? This problem arises in numerous applicatio ns in which topological information on intersection of pairs of interv als is accompanied by additional metric information on their order, di stance, or size. An important application is physical mapping, a centr al challenge in the human genome project. Our results are (1) a polyno mial algorithm for the problem on interval graphs which admit a unique clique order (UCO graphs). This class of graphs properly contains all prime interval graphs. (2) In case all constraints are upper and lowe r bounds on individual interval lengths, the problem on UCO graphs is linearly equivalent to deciding if a system of difference inequalities is feasible. (3) Even if all the constraints are prescribed lengths o f individual intervals, the problem is NP-complete. Hence, problems (1 ) and (2) are also NP-complete on arbitrary interval graphs.