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> ≥ 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> ≤ 10. We also prove several minor results.
Identifer | oai:union.ndltd.org:WATERLOO/oai:uwspace.uwaterloo.ca:10012/1174 |
Date | January 2006 |
Creators | Pan, Shengjun |
Publisher | University of Waterloo |
Source Sets | University of Waterloo Electronic Theses Repository |
Language | English |
Detected Language | English |
Type | Thesis or Dissertation |
Format | application/pdf, 414477 bytes, application/pdf |
Rights | Copyright: 2006, Pan, Shengjun. All rights reserved. |
Page generated in 0.0015 seconds