Papers
Two theorems on the minimum number of intersections for complete graphs
Author(s)Thomas Saaty
Joseph M. Katz Graduate School of Business
University of Pittsburgh
United States
Publication date: Jun, 1967
Journal: Journal of Combinatorial TheoryVol.: 2- Issue: 4- Pages: 571-584
Publisher: Journal of Combinatorial Theory
Abstract: After summarizing results of work on a conjecture regarding the minimum number of intersections of a complete graph drawn in the plane, the paper gives two theorems: one regarding a realization scheme for the conjectured quantity, and the other regarding a proof that essentially, the result would be minimal if it could be shown that a complete graph on n vertices with a minimum number of intersections contains a complete subgraph on n−2 vertices with a minimum number of intersections.
Keywords: Complete graph, Minumum number of intersections