An algorithm of graph planarity testing and cross minimization

Abstract

This paper presents an overview on one compartment from the graph theory, called graph planarity testing. It covers the fundamental concepts and important work in this area. Also a new approach is presented, which tests if a graph is planar in linear time O(n) and it can be used to determine the minimum crosses in a graph if it isn't planar.