Doctoral Thesis Defense: Recognizing Weak Embeddings

Abstract

An embedding of a graph G is a drawing phi:G->M of G on a surface M such that every vertex in V(G) is mapped to distinct points and each edge in E(G) to interior-disjoint Jordan arcs between the corresponding vertices. A weak embedding is a map phi:G->M if, for every eps>0, there exists an embedding psi:G->M so that ||phi-psi||<eps, where ||.|| is the uniform norm (i.e., sup norm). We say that the embedding psi approximates phi. The study of weak embeddings lies at the interface of several independent lines of research in mathematics and computer science. In particular, it generalizes various graph visualization models and is a special case of the notoriously difficult cluster-planarity problem. It is also related to the foldability problem in computational origami.

This thesis presents several results on the algorithmic complexity of recognizing weak embeddings.