Information Technology Reference
In-Depth Information
Ta b l e 1 .
Measurements of MapSets on test cases:
ALG and ALG
fd
stand for the ratio between the to-
tal ink of the drawing and the total length of the mini-
mum spanning trees after the steps
Tree Construction
and
Force-directed Adjustment
, respectively.
Tree Construction
Force-directed Adjustment
Edge Augmentation
graph
|P|
k
ALG ALG
fd
15
Colors
50
6
1
.
002
1
.
012
10
GD
506 23 1
.
582
1
.
612
Recipes
381 15 1
.
356
1
.
502
5
Trade
18
.
101
1
.
259
Universities
18
.
366
1
.
443
0
SODA
316 11 1
.
204
1
.
296
Colors
GD
Recipes
Trade
Universities
graph
IPL
336 11 1
.
337
1
.
414
SOCG
500 11 1
.
492
1
.
601
Fig. 8.
Running times of the different
steps of MapSets on some of the test
cases.
TA R J A N
252 16 1
.
150
1
.
197
ALGO
05
.
547
1
.
650
The algorithm is implemented in C++. We use a machine with Intel i5 3.2GHz and
8GB RAM for measuring running time; see Fig. 8. The last two steps,
Adding Auxiliary
Points
and
Computing Regions
, are very efficient taking few milliseconds for the largest
graphs, and hence are not included in the chart. The first step,
Tree Construction
,isusu-
ally the most time consuming; it is more efficient for nearly contiguousclusters (e.g,
Colors
) and less efficient for graphs with many fragments (e.g.,
GD
). Although
Edge
Augmentation
theoretically has cubic time complexity, it is among the fastest steps in
practice, because there are usually not many edges added. Overall, ouralgorithm pro-
cesses all the graphs (most with hundreds of vertices) in less than a minute. This is
slower than the GMap and LineSets but comparable to BubbleSets. Since ouralgorithm
extensively utilizes many primitive geometric operations (e.g., testing for segment in-
tersections), using a specialized geometric library will likely improve the performance.
6
Conclusion and Future Work
We d e s igned and implemented a new approach for visualizing embedded and clustered
graphs. Unlike existing techniques, our MapSets method always produces contiguous
and non-overlapping regions. Results of the initial evaluations seem promising.Wealso
presented a simple approximation algorithm for the geometric problem of ink minimiza-
tion motivated by the method. A natural future direction is to improve the approximation
factor. It would be also worthwhile to carefully evaluate different convexity measures and
select one that offers the best balance between ease of computation and visual quality
of the resulting regions. Similarly interesting would be in-depth user study comparing
map-based visualizations constructed with different approaches considered in the paper.
Acknowledgements.
The work supported in part by NSF grants CCF-1115971 and
DEB 1053573. We thank the authors of [17] for the DNA dataset. The drawingsof
KelpFusion are courtesy of the authors of [15].
