The minimum number of intersections in complete graphs
Joseph M. Katz Graduate School of Business
University of Pittsburgh
: Sep, 1964
: Proceedings of the National Academy of Sciences of the United States of AmericaVol.: 52- Issue: 3- Pages: 688
: Zarankiewicz has developed results concerning the minimum number of edge intersections, when drawn in a plane, of the bipartite graph consisting of two sets of vertices with one edge joining each element of one set to each element of the other set. When each set has three vertices, we have one of the two basic nonplanar graphs appearing in Kuratowski's theorem characterizing planar graphs.2 By generalizing on this graph, Zarankiewicz was able to establish his result and also to indicate a scheme for its realization.
: Graph theory, Complete graph