Çizge kuramında düzlemselliği test etme algoritmaları

Determining the planarity or displanarity of a graph and possibly embedding that graph is one of the most intriguing and fascinating algorithmic problems of the fields of graph theory and graph drawings. This thesis studies the simplest ways to do exactly that by using simple nevertheless efficient algorithms. Section 4 gives a short but comprehensive historical background on the subject by introducing a list of almost all planarity algorithms of all time. In this master thesis two linear-time algorithms and one quadratic-time algorithm are discussed. The presented algorithms are applied on two examples each to see which algorithm comes in handy when testing the planarity of a graph manually. According to the findings, the Boyer-Myrvold algorithm is the fastest algorithm to test the planarity of a certain graph, with few vertices, manually. However, based on tests done in LEDA (A Library of Efficient Data Types and Algorithms) on graphs with many vertices, the Left-Right planarity algorithm is the fastest algorithm to test planarity.