Skip to main content

Planarity Based Algorithms for Minor Embedding in Grid Graphs

Resource type
Thesis type
(Thesis) M.Sc.
Date created
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 statement
Copyright is held by the author.
This thesis may be printed or downloaded for non-commercial research and scholarly purposes.
Scholarly level
Supervisor or Senior Supervisor
Thesis advisor: Mitchell, David
Member of collection
Download file Size
etd9666_SEtezad.pdf 4.04 MB

Views & downloads - as of June 2023

Views: 0
Downloads: 0