NDLI: Angle-Restricted Steiner Arborescences for Flow Map Layout

Content Provider	Springer Nature Link
Author	Buchin, Kevin Speckmann, Bettina Verbeek, Kevin
Copyright Year	2014
Abstract	We introduce a new variant of the geometric Steiner arborescence problem, motivated by the layout of flow maps. Flow maps show the movement of objects between places. They reduce visual clutter by bundling curves smoothly and avoiding self-intersections. To capture these properties, our angle-restricted Steiner arborescences, or flux trees, connect several targets to a source with a tree of minimal length whose arcs obey a certain restriction on the angle they form with the source.We study the properties of optimal flux trees and show that they are crossing-free and consist of logarithmic spirals and straight lines. Flux trees have the shallow-light property. We show that computing optimal flux trees is NP-hard. Hence we consider a variant of flux trees which uses only logarithmic spirals. Spiral trees approximate flux trees within a factor depending on the angle restriction. Computing optimal spiral trees remains NP-hard, but we present an efficient 2-approximation, which can be extended to avoid “positive monotone” obstacles.
Starting Page	656
Ending Page	685
Page Count	30
File Format	PDF
ISSN	01784617
Journal	Algorithmica
Volume Number	72
Issue Number	2
e-ISSN	14320541
Language	English
Publisher	Springer US
Publisher Date	2014-01-23
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Steiner arborescences Flow maps Computational geometry Automated cartography Algorithm Analysis and Problem Complexity Theory of Computation Mathematics of Computing Algorithms Computer Systems Organization and Communication Networks Data Structures, Cryptology and Information Theory
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Angle-Restricted Steiner Arborescences for Flow Map Layout

Angle-restricted Steiner Arborescences for Flow Map Layout (2011)

Exact Algorithms for the Bottleneck Steiner Tree Problem

Approximation Schemes for Node-Weighted Geometric Steiner Tree Problems

Computing Optimal Steiner Trees in Polynomial Space

Minimum k Arborescences with Bandwidth Constraints

Algorithmic Aspects of Proportional Symbol Maps

Euclidean Prize-Collecting Steiner Forest

The Euclidean Bottleneck Full Steiner Tree Problem

Angle-Restricted Steiner Arborescences for Flow Map Layout

Similar Documents

Angle-Restricted Steiner Arborescences for Flow Map Layout

Angle-restricted Steiner Arborescences for Flow Map Layout (2011)

Exact Algorithms for the Bottleneck Steiner Tree Problem

Approximation Schemes for Node-Weighted Geometric Steiner Tree Problems

Computing Optimal Steiner Trees in Polynomial Space

Minimum k Arborescences with Bandwidth Constraints

Algorithmic Aspects of Proportional Symbol Maps

Euclidean Prize-Collecting Steiner Forest

The Euclidean Bottleneck Full Steiner Tree Problem

Angle-Restricted Steiner Arborescences for Flow Map Layout