Optimal algorithms for compact linear layouts

Research output: Contribution to conferenceAbstractAcademic

93 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

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

Cite this