Back to search

University of Waterloo

On the Crossing Numbers of Complete Graphs

Abstract

dc:description.abstract

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.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2006

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Pan, Shengjun

Subjects

dc:subject × 4

Rights

dc:rights
Statement dc:rights
  • Copyright: 2006, Pan, Shengjun. All rights reserved.
Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/1174

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Pan, Shengjun. On the Crossing Numbers of Complete Graphs. University of Waterloo, 2006. http://hdl.handle.net/10012/1174