Algebraic Methods And Graph Planarity Checking

This research is devoted to a graph planarity testing.There are 3 chapters.In the first chapter there are definitions,well-known graph algorithms like a DFS-algorithm,some of mathematical frameworks,which are used in the next chapters.In the second chapter is described a planarity process with using isometric cycles and rotation of graph vertices.And also is showed that a system of graph isometric cycles induces graph vertices spin for describing a topological scheme of a plane graph.In the third chapter is sketchy described a planarity testing algorithm with a drawing a topological scheme of a planar graph.In contrast to the classical planarity testing algorithms,e.g.the Hopcroft-Tarjan algorithm,the topological drawing obtained as a result of the proposed algorithm execution is used subsequently for the visualization of the planar graph.Computational complexity of the proposed algorithm is estimated by O(m~2),where m is the number of edges in the graph.