Skip to main content

Minor-embedding planar graphs in grid graphs

Resource type
Thesis type
(Thesis) M.Sc.
Date created
A recent development in solving challenging combinatorial optimization problems is the introduction of hardware that performs optimization by quantum annealing. Exploiting this hardware to solve a problem requires first solving a graph minor-embedding problem, which is also apparently intractable. Motivated by this application, we consider the special case of finding a minor-embedding of a planar graph in a grid graph. We introduce two algorithmic approaches to the problem, based on planarity-testing techniques. For one approach, we provide an implementation and an experimental evaluation demonstrating its potential.
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
etd9618_ETavakoli.pdf 3.96 MB

Views & downloads - as of June 2023

Views: 0
Downloads: 1