Drawing trees in a streaming model

被引：13

作者：

Binucci, Carla ^{[1
]}

Brandes, Ulrik ^{[2
]}

Di Battista, Giuseppe ^{[3
]}

Didimo, Walter ^{[1
]}

Gaertler, Marco ^{[4
]}

Palladino, Pietro ^{[5
]}

Patrignani, Maurizio ^{[3
]}

Symvonis, Antonios ^{[6
]}

Zweig, Katharina ^{[7
]}

机构：

[1] Univ Perugia, Dipartimento Ing Elettron & Informaz, I-06100 Perugia, Italy

[2] Univ Konstanz, Dept Comp & Informat Sci, Constance, Germany

[3] Univ Roma Tre, Dipartimento Informat & Automaz, Rome, Italy

[4] Univ Karlsruhe, Inst Theoret Comp Sci, Karlsruhe, Germany

[5] Univ Perugia, Dipartimento Med Sperimentale & Sci Biochim, I-06100 Perugia, Italy

[6] Natl Tech Univ Athens, Dept Math, GR-10682 Athens, Greece

[7] Heidelberg Univ, Interdisciplinary Ctr Sci Comp IWR, D-6900 Heidelberg, Germany

来源：

INFORMATION PROCESSING LETTERS | 2012年 / 112卷 / 11期

关键词：

Design of algorithms; Graph algorithms; Online algorithms; Graph drawing; Streaming; Large graphs; GRAPH;

D O I：

10.1016/j.ipl.2012.02.011

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We pose a new visualization challenge, asking Graph Drawing algorithms to cope with the requirements of Streaming applications. In this model a source produces a graph one edge at a time. When an edge is produced, it is immediately drawn and its placement cannot be altered. The drawing has an image persistence, that controls the lifetime of edges. If the persistence is k, an edge remains in the drawing for the time spent by the source to generate k edges, and then it fades away. In this model we study the area requirement of planar straight-line grid drawings of trees and we assess the output quality of the presented algorithms by computing the competitive ratio with respect to the best known offline algorithms. (C) 2012 Elsevier B.V. All rights reserved.

引用

页码：418 / 422

页数：5

共 20 条

[1] [Anonymous], 1999, GRAPH DRAWING ALGORI
[2] Bar-Yossef Z, 2002, SIAM PROC S, P623
[3] The minimum area of convex lattice n-gons
Bárány, I
Tokushige, N
[J]. COMBINATORICA, 2004, 24 (02) : 171 - 185
[4] A better heuristic for orthogonal graph drawings
Biedl, T
Kant, G
[J]. COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 1998, 9 (03): : 159 - 180
[5] Binucci C., 2009, Graph Drawing, P292
[6] Branke J., 2001, Drawing graphs. Methods and models (Lecture Notes in Computer Science Vol.2025), P228
[7] BURIOL L, 2005, P WORKSH MASS GEOM D, P9
[8] Crescenzi P., 1992, Computational Geometry: Theory and Applications, V2, P187, DOI 10.1016/0925-7721(92)90021-J
[9] De Pauw W, 1998, PROCEEDINGS OF THE FOURTH USENIX CONFERENCE ON OBJECT-ORIENTED TECHNOLOGIES AND SYSTEMS, P219
[10] HOW TO DRAW A PLANAR GRAPH ON A GRID
DEFRAYSSEIX, H
PACH, J
POLLACK, R
[J]. COMBINATORICA, 1990, 10 (01) : 41 - 51

← 1 2 →