A new optimal algorithm for outerplanar graph testing.
Date of Award
Tsin, Y. H.,
CC BY-NC-ND 4.0
A graph is a mathematical abstraction that is useful in solving a variety of problems. NP-complete (Non-deterministic Polynomial) problems are computational problems for which there is no known polynomial time algorithm solving them. Unfortunately, many important graph theoretic problems are known to be NP-Complete for arbitrary graph. However, for some classes of graphs, polynomial time algorithms have been discovered. Owing to this reason, it is of both theoretical and practical interest to be able to tell if a given graph belongs to one of those classes. As a result, graph recognition has received considerable attention over the last few decades. It is well known that the Hamiltonian cycle problem is NP-Complete. However, for the class of outerplanar graphs, polynomial time algorithms for the Hamiltonian cycle problem have been proposed. In this thesis, we shall first study existing outerplanarity testing algorithms, and present a new outerplanarity testing algorithm which is optimal and much simpler than existing algorithms. The new algorithm proposed in this thesis is based on the depth-first search, an ear decomposition technique and a vertex/edge absorb operation. It is conceptually simple and is easy to implement. A rigorous proof for the correctness of the new algorithm is presented and its time complexity is analyzed.Dept. of Computer Science. Paper copy at Leddy Library: Theses & Major Papers - Basement, West Bldg. / Call Number: Thesis2004 .L56. Source: Masters Abstracts International, Volume: 43-05, page: 1753. Adviser: Y. H. Tsin. Thesis (M.Sc.)--University of Windsor (Canada), 2004.
Lin, Yuanyuan., "A new optimal algorithm for outerplanar graph testing." (2004). Electronic Theses and Dissertations. 684.