The minimum number of intersections in complete graphs

Thomas Saaty
Joseph M. Katz Graduate School of Business
University of Pittsburgh
United States

Publication date: Sep, 1964

Journal: Proceedings of the National Academy of Sciences of the United States of America
Vol.: 52- Issue: 3- Pages: 688

Abstract: 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.

Keywords: Graph theory, Complete graph