Selected algorithms for planar graphs

W pracy przedstawiono implementację wybranych algorytmów dla grafów planarnych w języku Python. Poruszono trzy zagadnienia, dla których zawężenie się do grafów planarnych pozwoliło na stworzenie szybszych algorytmów niż dla ogólnych grafów.Zaimplementowano i omówiono dwa algorytmy znajdujące minimalne drzewo rozpinające: algorytm Cheritona-Tarjana oraz zmodyfikowany algorytm Boruvki. Algorytmy te uzyskują w praktyce liniową złożoność czasową mimo pewnych uproszczeń w implementacji. W pracy przedstawiono również algorytm 5-kolorowania wierzchołków grafu planarnego działający w~czasie liniowym. Algorytm ten wykorzystuje lemat dotyczący wierzchołków stopnia 5. Ostatnie zagadnienie dotyczy grafów szeregowo-równoległych skierowanych (dsp-grafów). Podano algorytm rozpoznawania dsp-grafów, oraz stworzono generatory przypadkowych dsp-grafów i dsp-drzew.Przygotowany kod źródłowy został sprawdzony z~użyciem testów jednostkowych języka Python. Sprawdzono również praktyczną złożoność obliczeniową i skalowalność algorytmów.

Python implementation of selected graph algorithms for planar graphs is presented in this document. It contains three topics where a restriction to planar graphs allowed the creation of faster algorithms then in the general case.Two algorithms finding the minimum spanning tree have been implemented and discussed: the Cheriton-Tarjan algorithm and the modified Boruvka algorithm. These algorithms achieve the approximate linear time complexity despite some simplications. The next one is the algorithm for 5-vertex-coloring of planar graphs. This algorithm achieves linear time complexity thanks to the properties of 5-degree vertices. The last topic deals with directed series-parallel graphs (dsp-graphs).The algorithm for recognizing dsp-graphs is prepared. Generators for random dsp-graphs and random dsp-trees are also built.The Python unit testing tools were used to check the source code. The real computational complexity and scalability were also tested.