Papers
The minimum number of intersections in complete graphs
Author(s)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 AmericaVol.: 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