I just added a new article to Wikipedia on indifference graphs (also known as unit interval graphs or proper interval graphs): the graphs formed from sets of points on the real line by connecting every two points whose distance is less than one.

Indifference graph

There are many papers on algorithms for going from the graph to a geometric representation in linear time. The following method for the reverse problem, going from the set of points (or equivalently unit intervals) to its graph must be known, possibly in the context of its generalization to higher dimensional unit disk graphs, but I don't know a good reference for it.

Given a set of real numbers:

  1. Round each one down to the nearest smaller integer.

  2. Use a hash table to collect numbers that round to the same integer.

  3. For each number \( x \), use the hash table to find each other number \( y \) whose rounded value is within one of the rounded value of \( x \).

  4. Create an edge in the graph for every pair \( (x,y) \) found in this way whose distance is at most one.

Each pair \( (x,y) \) can be charged against the hash table entry of \( x \) or \( y \) that has the larger number of inputs mapped to it. In this way, each hash table entry gets a charge proportional to the square of its number of values. But on the other hand every pair of inputs that map to the same hash table entry form an edge, so the number of edges is at least proportional to the sum of the squares of the hash table entry sizes. Thus, the total work is at most proportional to the total output size.

Update, April 22: It appears that the correct reference for this is: Bentley, Jon L.; Stanat, Donald F.; Williams, E. Hollins, Jr. The complexity of finding fixed-radius near neighbors. Information Processing Lett. 6 (1977), no. 6, 209–212.




Comments:

hlwoods:
2014-04-21T19:31:12Z

Do you need a hash table? Can you assume the list of integers is sorted?

If the list is sorted, you can find the edges just by traversing the sorted list and edges as you encounter them.

11011110:
2014-04-21T20:11:42Z

True, but the point of the hash table is to avoid nonlinear time bounds for sorting.

brooksmoses:
2014-04-22T06:55:43Z

Ah, and you use a hash table rather than an array of lists because that way you can bound the size a priori (and you also avoid time dependencies on the maximal spacing between points), yes?

11011110:
2014-04-22T07:23:00Z

Yes, the gaps can be huge, so an array might be too big.

None:
2014-04-22T14:37:40Z

There is a missing word there : "The bandwidth of an arbitrary graph G is one than the size of" , I could correct it but I am not sure whether it is "more" or "less"

11011110:
2014-04-22T15:16:36Z

One less. Thanks for catching that.