Algoritem za oktilinearno shematizacijo omrežij

magistrsko delo

Domen Keglevič (Avtor), Borut Robič (Mentor)

Povzetek

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.

Ključne besede

algoritmi;risanje grafov;celoštevilsko programiranje;

Podatki

Jezik:	Slovenski jezik
Leto izida:	2021
Tipologija:	2.09 - Magistrsko delo
Organizacija:	UL FRI - Fakulteta za računalništvo in informatiko
Založnik:	[D. Keglevič]
UDK:	004.4
COBISS:	75340291
Št. ogledov:	733
Št. prenosov:	34
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	Algorithm for octilinear schematization of network drawings
Sekundarni povzetek:	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.
Sekundarne ključne besede:	algorithms;graph drawing;integer programming;
Vrsta dela (COBISS):	Magistrsko delo/naloga
Študijski program:	0
Komentar na gradivo:	Univ. v Ljubljani, Fak. za matematiko in fiziko, Oddelek za matematiko, Računalništvo in matematika - 2. stopnja
Strani:	VII, 66 str.
ID:	13349319