Optimal algorithms for compact linear layouts

Onderzoeksoutput: Bijdrage aan congresAbstract

44 Downloads (Pure)


Linear layouts are a simple and natural way to draw a graph: all vertices are placed on a single line and edges are drawn as arcs between the vertices. Despite its simplicity, a linear layout can be a very meaningful visualization if there is a particular order defined on the vertices. Common examples of such ordered - and often also directed - graphs are event sequences and processes: public transport systems tracking passenger check-in and check-out, banks checking online transactions, or hospitals recording the paths of patients through their system, to name a few. A main drawback of linear layouts are the usually (very) large aspect ratios of the resulting drawings, which prevent users from obtaining a good overview of the whole graph. In this paper we present a novel and versatile algorithm to optimally fold a linear layout of a graph such that it can be drawn effectively in a specified aspect ratio, while still clearly communicating the linearity of the layout.
Originele taal-2Engels
Aantal pagina's6
StatusGepubliceerd - 22 mrt 2018
Evenement34th European Workshop on Computational Geometry (EuroCG2018) - Berlin, Duitsland
Duur: 21 mrt 201823 mrt 2018


Congres34th European Workshop on Computational Geometry (EuroCG2018)
Verkorte titelEuroCG2018
Internet adres


Citeer dit

Meulemans, W., Sonke, W., Speckmann, B., Verbeek, E., & Verbeek, K. (2018). Optimal algorithms for compact linear layouts. 10:1-10:6. Abstract van 34th European Workshop on Computational Geometry (EuroCG2018), Berlin, Duitsland.