Return to search

On the Crossing Numbers of Complete Graphs

In this thesis we prove two main results. The Triangle Conjecture asserts that the convex hull of any optimal rectilinear drawing of <em>K<sub>n</sub></em> must be a triangle (for <em>n</em> &ge; 3). We prove that, for the larger class of pseudolinear drawings, the outer face must be a triangle. The other main result is the next step toward Guy's Conjecture that the crossing number of <em>K<sub>n</sub></em> is $(1/4)[n/2][(n-1)/2][(n-2)/2][(n-3)/2]$. We show that the conjecture is true for <em>n</em> = 11,12; previously the conjecture was known to be true for <em>n</em> &le; 10. We also prove several minor results.

Identiferoai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:OWTU.10012/1174
Date January 2006
CreatorsPan, Shengjun
PublisherUniversity of Waterloo
Source SetsLibrary and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada
LanguageEnglish
Detected LanguageEnglish
TypeThesis or Dissertation
RightsCopyright: 2006, Pan, Shengjun. All rights reserved.

Page generated in 0.002 seconds