Angle-restricted Steiner arborescences for flow map layout

Research output: Contribution to conferenceAbstractAcademic

153 Downloads (Pure)


Flow maps visualize the movement of objects between places. One or more sources are connected to several targets by arcs whose thickness corresponds to the amount of flow between a source and a target. Flow maps reduce visual clutter by merging (bundling) lines smoothly and by avoiding self-intersections. We present algorithms that compute crossing-free flows of high visual quality. To this end we introduce a new variant of the geometric Steiner arborescence problem. The goal is to connect the targets to a source with a tree of minimal length whose arcs obey a certain restriction on the angle they form with the source. Such an angle-restricted Steiner arborescence, or simply ow tree, naturally induces a clustering on the targets and smoothly bundles arcs. We study the properties of optimal flow trees and show that they consist of logarithmic spirals and straight lines. Computing optimal flow trees is NP-hard. Hence we consider a variant of flow trees which uses only logarithmic spirals, so called spiral trees. Spiral trees approximate flow trees within a factor depending on the angle restriction. Computing optimal spiral trees remains NP-hard. We present an efficient 2-approximation for spiral trees, which can be extended to avoid certain types of obstacles.
Original languageEnglish
Publication statusPublished - 2011
Event27th European Workshop on Computational Geometry (EuroCG 2011) - Morschach, Switzerland
Duration: 28 Mar 201130 Mar 2011
Conference number: 27


Workshop27th European Workshop on Computational Geometry (EuroCG 2011)
Abbreviated titleEuroCG


Dive into the research topics of 'Angle-restricted Steiner arborescences for flow map layout'. Together they form a unique fingerprint.

Cite this