Date of Award

Spring 2021

Degree Type

Thesis

Department

Mathematics

Director of Thesis

Éva Czabarka

First Reader

László Székely

Second Reader

László Székely

Abstract

The goal of this thesis is to compute upper and lower bounds on the biplanar crossing numbers of complete bipartite graphs. The concept of a biplanar crossing number was first introduced by Owens (Owens 1971) as an optimization problem in circuit design. To prove upper bounds, we follow a method used by Czabarka et. al. (Czabarka et. al. 2006), in which they start from an optimal drawing of a small bipartite graph and use it to generate drawings of larger bipartite graphs. We explore several possibilities for computing lower bounds. One is using Ramsey theory, via the Bipartite Ramsey Number and the Connected Bipartite Ramsey Number. We prove that these numbers are equal for complete bipartite graphs, except in a few trivial cases. The other method we use is a heavily computer-aided derivation, based on the counting method, of lower bounds for small complete bipartite graphs. This is the method used in Shavali and Zarrabi-Zadeh (Shavali and Zarrabi-Zadeh 2019). We present a slight improvement over their results.

First Page

1

Last Page

44

Rights

© 2021, Sydney Miyasaki

Download

Share

COinS