Optimal algorithms for compact linear layouts

Research output: Contribution to conferenceAbstractAcademic

154 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.
Original languageEnglish
Number of pages6
Publication statusPublished - 22 Mar 2018
Event34th European Workshop on Computational Geometry (EuroCG2018) - Berlin, Germany
Duration: 21 Mar 201823 Mar 2018


Conference34th European Workshop on Computational Geometry (EuroCG2018)
Abbreviated titleEuroCG2018
Internet address


Dive into the research topics of 'Optimal algorithms for compact linear layouts'. Together they form a unique fingerprint.

Cite this