Back to search

University of Victoria (Canada)

A faster algorithm for torus embedding

Abstract

dc:description.abstract

Although theoretically practical algorithms for torus embedding exist, they have not yet been successfully implemented and their complexity may be prohibitive to their practicality. We describe a simple exponential algorithm for embedding graphs on the torus (a surface shaped like a doughnut) and discuss how it was inspired by the quadratic time planar embedding algorithm of Demoucron, Malgrange and Pertuiset. We show that it is faster in practice than the only fully implemented alternative (also exponential) and explain how both the algorithm itself and the knowledge gained during its development might be used to solve the well-studied problem of finding the complete set of torus obstructions.

Degree

thesis:*
Level thesis:degree_level
Master of Science M.Sc.
Department thesis:degree_department
Department of Computer Science
Year dc:date.issued
2007

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Woodcock, Jennifer Roselynn
Advisors dc:contributor.supervisor
  • Myrvold, Wendy
  • Ruskey, Frank

Subjects

dc:subject × 7

Rights

dc:rights
Statement dc:rights
  • Available to the World Wide Web
Language dc:language.iso
en, English

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1828/130

Chain of custody

source
Harvested from
University of Victoria (Canada)
Base URL
dspace.library.uvic.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Woodcock, Jennifer Roselynn. A faster algorithm for torus embedding. Master of Science M.Sc. thesis, 2007. http://hdl.handle.net/1828/130