Algorithm for octilinear schematization of network drawings

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.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