Planarity testing of a graph

Abstract

Graphs provide a way to model connections between objects in different systems, e.g., roads, power grids, and networks. Mathematically graphs are structures that present a set of elements and their connections. Typically, graphs are illustrated graphically by denoting the elements by dots and the connections between them by lines. Graph theory and the properties associated to graphs will give a new approach so that it can be used as tool to reformulate different problems.

This thesis focuses on the results that can be used to test if a given graph is planar or not. A graph is planar if we can give it a graphical illustration in a plane so that the lines connecting the elements do not intersect. The thesis presents some fundamental properties of the planar graphs. A particularly important result is the Kuratowski's theorem, which gives a necessary and sufficient condition for a graph to be planar in terms of certain minor graphs called Kuratowski's minors.

A planarity testing algorithm is presented as a major result of this thesis. Its functionality is illustrated by an example that explains in detail how the algorithm constructs a representation of the graph in a plane with no intersecting lines or returns a Kuratowski's minor if the graph is not planar. then, some properties of planar graphs were reviewed, for example number of edges in a planar graph which is bounded to the number of vertices. And finally, after defining coloring of a graph, coloring property of planar graphs were review, such as them being 5 and 4-colorable.