Skip to main content

A Practical Torus Embedding Algorithm and Its Implementation

Resource type
Thesis type
(Thesis) M.Sc.
Date created
2014-06-13
Authors/Contributors
Author: Yu, Jiahua
Abstract
Embedding graphs on the torus is a problem with both theoretical and practical significance. It is required to embed a graph on the torus for solving many application problems in graphs. Such problems appear in disciplines including VLSI design and graph drawing. Although polynomial time algorithms for embedding graphs on the torus exist, they are complex and no working implementation exists. To develop a practical tool for embedding graphs on the torus, we propose a new algorithm with exponential running time. Compared with a previous well known exponential time algorithm, our algorithm has better practical performance. Furthermore, we show that our implementation covers most modules of a polynomial time algorithm and can serve as a good foundation for its implementation.
Document
Identifier
etd8431
Copyright statement
Copyright is held by the author.
Permissions
The author granted permission for the file to be printed and for the text to be copied and pasted.
Scholarly level
Supervisor or Senior Supervisor
Thesis advisor: Gu, Qianping
Member of collection
Download file Size
etd8431_JYu.pdf 1.79 MB

Views & downloads - as of June 2023

Views: 0
Downloads: 0