Daniel Aricatt: Book Embeddings of Graphs

Abstract: A book is a topological structure consisting of half planes (called pages) joined along a common boundary (called spine). Graphs are embedded on books by placing its vertices along the spine and the edges along a single page. The talk generalises books to a higher genus and studies the embeddings of graphs on it and the algorithmic complexities of questions related to it. We also look at the embeddings of infinite graphs by formalising book embeddings in first order logic.