Master’s Thesis Presentation • Algorithms and Complexity — Bounds on Maximum Matchings in 1-Planar Graphs
John Wittnebel, Master’s candidate
David R. Cheriton School of Computer Science
In this thesis, we study lower bounds on maximum matchings in 1-planar graphs. We expand upon the tools used for proofs of matching bounds in other classes of graphs as well as some original ideas in order to find these bounds. The first novel results we provide are lower bounds of maximum matching in 1-planar graphs as a function of their minimum degree.
Pedro Velmovitsky, Public Health and Health Systems
University of Waterloo