izpis_h1_title_alt

Algoritem za oktilinearno shematizacijo omrežij : magistrsko delo
ID Keglevič, Domen (Avtor), ID Robič, Borut (Mentor) Več o mentorju... Povezava se odpre v novem oknu

.pdfPDF - Predstavitvena datoteka, prenos (1,39 MB)
MD5: 5C936568DBA1D76B2076974F162D373D

Izvleček
Risba grafa, ki ima povezave narisane z vodoravnimi, navpičnimi in diagonalnimi daljicami, se imenuje oktilinearna risba. Takšne risbe veljajo za pregledne in se pogosto uporabljajo za prikaz geografskih omrežij kot je zemljevid podzemne železnice večjih mest. Zaradi števila omrežij in raznolikosti risb nastane potreba po njihovem avtomatskem generiranju. Izkaže se, da je to računsko zahteven problem in algoritmi, ki to počnejo morajo narediti kompromis med časovno zahtevnostjo in kvaliteto izhoda. V tej magistrski nalogi je predstavljen nov algoritem, ki problem razdeli na dva koraka. Najprej generira risbo, ki je oktilinearna in ima vozlišča na istih koordinatah kot vhodni podatki. Nato takšno risbo izboljšuje s spreminjanjem dolžin povezav. To je formulirano v obliki linearnega celoštevilskega programa. Izkaže se, da ima tak pristop več zaželjenih lastnosti in da je njegova časovna zahtevnost konkurenčna v primerjavi z drugimi pristopi.

Jezik:Slovenski jezik
Ključne besede:Algoritmi, risanje grafov, celoštevilsko programiranje
Vrsta gradiva:Magistrsko delo/naloga
Organizacija:FMF - Fakulteta za matematiko in fiziko
Leto izida:2021
PID:20.500.12556/RUL-129881 Povezava se odpre v novem oknu
COBISS.SI-ID:75340291 Povezava se odpre v novem oknu
Datum objave v RUL:09.09.2021
Število ogledov:608
Število prenosov:33
Metapodatki:XML RDF-CHPDL DC-XML DC-RDF
:
Kopiraj citat
Objavi na:Bookmark and Share

Sekundarni jezik

Jezik:Angleški jezik
Naslov:Algorithm for octilinear schematization of network drawings
Izvleček:
Graph drawing with edges that consist of horizontal, vertical and diagonal finite lines is called octilinear drawing. Such drawings are considered clear and easy to read and are often used to represent networks such as metro maps. Because of large number of networks and different features that can be put on a drawing, there is a need to generate them automatically. However, this is computationally expensive and algorithms that aim to do this must make tradeoffs between efficiency and quality of the result. Here we present a new algorithm which generates octilinear drawing from geographical data in two steps. In the first step it generates octilinear map which has unchanged coordinates of original vertices. In the second step it improves upon result of the first step by correcting edge lengths. This is formulated as an integer linear program. This algorithm has many beneficial properties and its running time is competitive with several other approaches.

Ključne besede:Algorithms, graph drawing, integer programming

Podobna dela

Podobna dela v RUL:
Podobna dela v drugih slovenskih zbirkah:

Nazaj