We present heuristic algorithms for minor embedding planar graphs in grids. Our work is motivated by the development of quantum computing hardware that performs quantum annealing. This hardware can be used to solve hard combinatorial problems, but requires the graph of each problem instance to be minor embedded in a graph that models the hardware. Hence, there is a need for practical minor embedding algorithms. We restrict our attention to planar graphs, and thus are able to make use of existing graph drawing methods. We present two algorithms for minor embedding planar graphs in grid graphs, and provide an experimental evaluation of one.
Copyright is held by the author.
This thesis may be printed or downloaded for non-commercial research and scholarly purposes.
Supervisor or Senior Supervisor
Thesis advisor: Mitchell, David
Member of collection