The Houses and Utilities Crossing Problem

The edges that connect each utility (green disks) to each house (blue squares) are in a single color. Each house in turn has a spectrum of colored edges that connect it to each utility. The red points are crossing points of utility lines. The object is to minimize the number of crossings for a particular set of utilities and houses by shifting their locations.

The minimal known number of crossings for 6, 7, 8, …, 14 houses and utilities is 1, 2, 4, 8, 16, 24, 36, 54, 77-81. The exact value of the last, for seven houses and seven utilities, has been a long unsolved question.