prikaz prve stranice dokumenta Ispitivanje svojstva planarnosti grafa
No public access
undergraduate thesis
Ispitivanje svojstva planarnosti grafa
Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing, 2022. urn:nbn:hr:168:114001
Mišak, Simona
University of Zagreb
Faculty of Electrical Engineering and Computing

Institutional repository: FER Repository

Cite this document

Mišak, S. (2022). Ispitivanje svojstva planarnosti grafa (Undergraduate thesis). Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing. Retrieved from https://urn.nsk.hr/urn:nbn:hr:168:114001

Mišak, Simona. "Ispitivanje svojstva planarnosti grafa." Undergraduate thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, 2022. https://urn.nsk.hr/urn:nbn:hr:168:114001

Mišak, Simona. "Ispitivanje svojstva planarnosti grafa." Undergraduate thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, 2022. https://urn.nsk.hr/urn:nbn:hr:168:114001

Mišak, S. (2022). 'Ispitivanje svojstva planarnosti grafa', Undergraduate thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, accessed 17 July 2024, https://urn.nsk.hr/urn:nbn:hr:168:114001

Mišak S. Ispitivanje svojstva planarnosti grafa [Undergraduate thesis]. Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing; 2022 [cited 2024 July 17] Available at: https://urn.nsk.hr/urn:nbn:hr:168:114001

S. Mišak, "Ispitivanje svojstva planarnosti grafa", Undergraduate thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, Zagreb, 2022. Available at: https://urn.nsk.hr/urn:nbn:hr:168:114001

Metadata
TitleIspitivanje svojstva planarnosti grafa
Title (english)Planarity Testing
AuthorSimona Mišak
MentorAnamari Nakić (mentor)
Committee memberAnamari Nakić (predsjednik povjerenstva)
Committee memberMarina Furkes (član povjerenstva)
Committee memberFilip Martinović (član povjerenstva)
GranterUniversity of Zagreb
Faculty of Electrical Engineering and Computing
Zagreb
Defense date and country2022-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
Keywords (english)
Languagecroatian
URN:NBNurn:nbn:hr:168:114001
Study programmeTitle: 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 resourceText
File originBorn digital
Access conditionsClosed access
Terms of useLicence In copyright icon
Public note
Created on2023-01-14 21:14:05