This thesis treats some of the problems related to the good drawings D$ sb{ rm n}$ of the complete graph K$ sb{ rm n}$. The first of these problems is obtaining all the non-isomorphic good drawings D$ sb{ rm n}$ of K$ sb{ rm n}$. After conjecturing that any good drawing D$ sb{ rm n}$ of K$ sb{ rm n}$ has at least one crossing-free Hamiltonian Circuit, an algorithm generating all the non-isomorphic good drawings D$ sb{ rm n}$ of K$ sb{ rm n}$ is developed. The second problem, determining the existence of a rectilinear drawing D$ sb{ rm n}$ of K$ sb{ rm n}$ with a given set of crossings, is solved by finding a characteristic of the rectilinear drawings D$ sb{ rm n}$ of K$ sb{ rm n}$. An algorithm using this characteristic determines whether a given set of crossing defines a rectilinear drawing D$ sb{ rm n}$ of K$ sb{ rm n}$. The last problem, to generate all the non-isomorphic rectilinear drawings D$ sb{ rm n}$ of K$ sb{ rm n}$, is solved by an algorithm using a set of rectilinear drawings D$ sb{ rm n-1}$ of K$ sb{ rm n-1}$.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMM.75756 |
| Date | January 1988 |
| Creators | Rafla, Nabil H. |
| Publisher | McGill University |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
| Format | application/pdf |
| Coverage | Doctor of Philosophy (School of Computer Science.) |
| Rights | All items in eScholarship@McGill are protected by copyright with all rights reserved unless otherwise indicated. |
| Relation | alephsysno: 000665174, proquestno: AAINL46123, Theses scanned by UMI/ProQuest. |
Page generated in 0.0018 seconds