Physical Sciences and Mathematics Commons^™

Survey Of Graph Embeddings Into Compact Surfaces, Sophia N. Potoczak

Electronic Theses and Dissertations

A prominent question of topological graph theory is "what type of surface can a nonplanar graph be embedded into?" This thesis has two main goals. First to provide a necessary background in topology and graph theory to understand the development of an embedding algorithm. The main purpose is developing and proving a direct constructive embedding algorithm that takes as input the graph with a particular order of edges about each vertex. The embedding algorithm will not only determine which compact surface the graph can be embedded into, but also determines the particular embedding of the graph on the surface. The …