Straight-line realization of planar graphs. - UBC Library Open Collections

UBC Theses and Dissertations

Featured Collection

UBC Theses and Dissertations

Straight-line realization of planar graphs. Shiau, Luang-hung

Abstract

Few theorems are known about planar graphs. For, example, Kuratowski proved that a graph is planar if and only if it has no subgraph homeomorphic to K₅ or K₃,₃. It has remained as a direct criterion for determining whether a graph is planar or not. Powerful as the theorem is, it is not always easy to apply. This leads us to try some practical methods to test a planar graph. In this thesis, we have an algorithm for finding an outer circuit for a simple connected planar graph. Then, we use this outer circuit to draw a straight line graph in the plane. The programme for this algorithm is written in FORTRAN for an IBM 360/67 Computer.

Item Metadata

Title	Straight-line realization of planar graphs.
Creator	Shiau, Luang-hung
Publisher	University of British Columbia
Date Issued	1971
Description	Few theorems are known about planar graphs. For, example, Kuratowski proved that a graph is planar if and only if it has no subgraph homeomorphic to K₅ or K₃,₃. It has remained as a direct criterion for determining whether a graph is planar or not. Powerful as the theorem is, it is not always easy to apply. This leads us to try some practical methods to test a planar graph. In this thesis, we have an algorithm for finding an outer circuit for a simple connected planar graph. Then, we use this outer circuit to draw a straight line graph in the plane. The programme for this algorithm is written in FORTRAN for an IBM 360/67 Computer.
Genre	Thesis/Dissertation
Type	Text
Language	eng
Date Available	2011-05-03
Provider	Vancouver : University of British Columbia Library
Rights	For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.
DOI	10.14288/1.0051252
URI	http://hdl.handle.net/2429/34212
Degree	Master of Science - MSc
Program	Computer Science
Affiliation	Science, Faculty of; Computer Science, Department of
Degree Grantor	University of British Columbia
Campus	UBCV
Scholarly Level	Graduate
Aggregated Source Repository	DSpace

Item Media

UBC_1971_A6_7 S55.pdf -- 5MB

Item Citations and Data

Rights

For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.