Ispitivanje svojstva planarnosti grafa

undergraduate thesis

• Title (english): Planarity Testing
• Author: Simona Mišak
• Mentor: Anamari Nakić (mentor)
• Committee member: Anamari Nakić (predsjednik povjerenstva)
• Committee member: Marina Furkes (član povjerenstva)
• Committee member: Filip Martinović (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2022-07-01, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

Graf je planaran ako se može smjestiti u ravninu bez presijecanja bridova, tj. tako da se dva brida geometrijski ne sijeku niti u jednoj točki, osim eventualno u vrhu s kojim su oba incidentni. Ispitivanje planarnosti grafa je ponekad težak računarski problem. Postoje brojni algoritmi te metode koje se bave tim problemom. Metode se razlikuju ovisno o osnovnoj jedinici dodavanja u ravninski prikaz. Tako postoje metoda dodavanja puta, vrha te brida. Boyer-Myrvold algoritam, jedan od najpoznatijih i najčešće korištenih algoritama, implementira metodu dodavanja brida. Taj je algoritam uz pomoć Boost biblioteke implementiran u aplikaciji u sklopu ovog rada. Ta aplikacija ispituje planarnost zadanog grafa te klasificira sve planarne grafove za zadani broj vrhova n, gdje je n=1, 2, 3, 4, 5.

Abstract (english)

The graph is planar if it can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Testing the properties of planar graphs is often a difficult computing problem. There are many algorithms and methods that deal with this problem. These methods differ based on the unit of addition in the planar embedding and so there exist path addition, vertex addition and edge addition method. The Boyer-Myrvold algorithm, one of the most popular and most frequently used algorithms, uses the latter one. It is implemented in Boost library, that is used in the application developed for this paper. This application tests whether the given graph is planar. It also classifies all planar graphs for n number of vertices, where n=1, 2, 3, 4, 5.

• Keywords: teorija grafova; planaran graf; algoritmi za ispitivanje planarnosti grafa
• Keywords (english): graph theory; planar graph; planarity testing algorithms
• Language: croatian
• URN:NBN: urn:nbn:hr:168:114001
• Study programme: Title: Computing; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2023-01-14 21:14:05