# An early reference on crossing minimization

The crossing number of a graph is the minimum number of edge crossings with which it can be drawn. A lot of research in graph drawing has involved algorithms or heuristics for minimizing this number, because drawings with more crossings tend to be less understandable.

The traditional story of crossing numbers is that they began with Turán's "brick factory problem", named after the brick factory in which Hungarian mathematician Pál Turán was imprisoned by the Nazis during World War II, and his musings on how to design a system of tracks that would have as few crossings as possible. But it turns out (as I found today while looking for something else) the same problem was percolating at the same time in an entirely different field of study: sociology. In 1934, J. L. Moreno invented the sociogram, and in 1944, Urie Bronfenbrenner wrote (about how to place the vertices in such a drawing): "The arrangement of subjects on the diagram, while haphazard in part, is determined largely by trial and error with the aim of minimizing the number of intersecting lines." Crossing numbers!

I haven't yet tracked down an online copy of Moreno's original publication, or what he says about vertex placement in it (the 1953 second edition is here), but Bronfenbrenner's can be found at JSTOR: Bronfenbrenner, Urie (1944). "The graphic presentation of sociometric data". *Sociometry* 7 (3): 283–289.