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