Back to search

University of Waterloo

Simple Drawings of Kn from Rotation Systems

Abstract

dc:description.abstract

A complete rotation system on n vertices is a collection of n cyclic permutations of the elements [n]\{i}, for i∈[n]. If D is a drawing of a labelled graph, then a rotation at vertex v is the cyclic ordering of the edges at v. In particular, the collection of all vertex rotations of a simple drawing of Kn is a complete rotation system. Can we characterize when a complete rotation system can be represented as a simple drawing of Kn (a.k.a. realizable)? This thesis is motivated by two specific results on complete rotation systems. The first motivating theorem was published by Kyncl in 2011, who, using homotopy, proved as a corollary that if all complete 6-vertex rotation systems of a complete n-vertex rotation system H are realizable, then H is realizable. Combined with communications with Aichholzer, Kyncl determined that complete realizable n-vertex rotation systems are characterized by their complete 5-vertex rotation systems. The second motivating theorem was published by Gioan in 2005, he proved that if two simple drawings of the complete graph D and D′ have the same rotation system, then there is a sequence of Reidemeister III moves that transforms D into D′. Motivated by these results, we prove both facts combinatorially by sequentially drawing the edge crossings of an edge to form a simple drawing. Such a method can be used to prove both theorems, generate every simple drawing of a complete rotation system, or find a non-realizable complete 5-vertex rotation system in any complete rotation system (when one exists).

Degree

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

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Sullivan, Matthew A.
Advisor dc:contributor.advisor
  • Richter, R. Bruce

Subjects

dc:subject × 4

Rights

Language dc:language.iso
en

Identifiers

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

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

Sullivan, Matthew A.. Simple Drawings of Kn from Rotation Systems. University of Waterloo, 2021. http://hdl.handle.net/10012/17627