Study of outerplanar graphs with Python

W pracy zostały przedstawione niezbędne zagadnienia z teorii grafów pozwalające na zdefiniowanie grafów zewnętrznie planarnych oraz ich właściwości. Graf zewnętrznie planarny jest to graf, który można narysować na płaszczyźnie tak, aby wszystkiego jego wierzchołki leżały na jego ścianie zewnętrznej, a krawędzie nie przecinały się.W dalszej części zostały zaimplementowane wybrane algorytmy dotyczące tej klasy grafów, to jest algorytm rozpoznawania grafów zewnętrznie planarnych, kolorowania wierzchołków, podziału dowolnego grafu na dwuspójne składowe, sprawdzania czy graf zewnętrznie planarny jest hamiltonowski, wyznaczenie długości najdłuższego cyklu, oraz generowanie maksymalnych grafów zewnętrznie planarnych. Algorytmy zostały zaimplementowane przy użyciu języka Pythonoraz biblioteki graphtheory. Stworzony kod działa wPythonie 2.7 i Pythonie 3.9, co zapewnia jego uniwersalność.Poprawność implementacji algorytmów sprawdzono poprzez testy jednostkowe z wykorzystaniem modułu unittest.Sprawdzono również rzeczywistą wydajność wszystkich algorytmówz użyciem modułu timeit. Testy potwierdziły zgodność z przewidywaniami teoretycznymi.

This work presents the necessary issues from the graph theory, which allow us to define outerplanar graphs with their properties.An outerplanar graph is a graph that has a planar drawing such thatall vertices belong to the outer face and no edges cross each other.In the following part, selected algorithms are implemented for this class of graphs. There is the recognition algorithm, finding biconnected components, recognition of hamiltonian graphs in the class of outerplanar graphs, finding the longest cycle, optimal vertex coloring algorithm, and maximal outerplanar graphs generator.Python implementation of the algorithms is included, where the graphtheory package is used. Code may be executed in Python 2.7 and Python 3.7, so it is universal.Correctness of algorithms was checked using unit testingwith the unittest module. The real computational complexity of all algorithms was also checked by means of the timeit module.