Algoritmi za ispitivanje planarnosti grafova

diplomski rad

• Naslov (engleski): Graph Planarity Testing Algorithms
• Autor: Ivan Vranjić
• Mentor: Mario Osvin Pavčević (mentor)
• Član povjerenstva: Mario Osvin Pavčević (predsjednik povjerenstva)
• Član povjerenstva: Domagoj Kovačević (član povjerenstva)
• Član povjerenstva: Maja Resman (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2015-07-13, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

Navedeni kriteriji planarnosti grafa. Naveden popis postojećih algoritama za testiranje. Analizirani i implementirani Demoucronov algoritam kvadratne vremenske složenosti i vertex addition algoritam linearne vremenske složenosti. Za vizualni prikaz planarnog grafa korišten Schnyderov algoritam.

Sažetak (engleski)

Introduction to planarity. Brief review of existing planarity testing algorithms. Analysed and implemented Demoucron's algorithm which has quadratic time complexity and vertex addition algorithm which has linear time complexity. Schnyder's algorithm is used for visual representation of planar graph.

• Ključne riječi: planarnost; testiranje planarnosti; Demoucron; st-numeriranje; vertex addition; PQ-stablo; Schnyder
• Ključne riječi (engleski): planarity; planarity testing; Demoucron; st-numbering; vertex addition; PQ-tree; Schnyder
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:592958
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra inženjer/inženjerka računarstva (mag.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2018-02-06 14:23:33