Information Technology Reference
In-Depth Information
GraphBook: Making Graph Paging Real
Alessio Arleo
1
,FeliceDeLuca
1
,Giuseppe Liotta
1
,
Fabrizio Montecchiani
1
, and Ioannis G. Tollis
2
1
Dip. di Ingegneria, Universit`adegli Studi di Perugia, Italy
2
University of Crete and Institute of Computer Science-FORTH, Greece
In the last years we observed an impressive growth of different mobile devices, like
tablets and smartphones, that allow people to access and share a large variety of con-
tents. These devices are often used to access social networks, route networks, or other
kinds of networks that for example may deal with the job of the user. Althoughdesign-
ing drawing algorithms and visualization systems tailored for mobile devices would be
the best choice in this case (see, e.g., [1]), this is often not possible, as for example the
drawing of the network might be computed by some diagram server in a collaborative
environment, or attached to an e-mail, or returned by a web application that does not
consider limited display capabilities. We present a system whose goal is to facilitate the
reading of a given drawing on a mobile device by exploiting an analogy with electronic
books
1
. It takes as inputadrawing
ʓ
of a graph
G
=(
V,E
) and computes a
graph book
B
(
ʓ
). The idea is to adapt the drawing's aspect-ratio to the device display and distribute
the visual complexity of the drawing in different pages that are browsed by using stan-
dard gestures. This is done in three steps. We describe two possible implementations for
each step, depending on whether
ʓ
is a straight-line drawing or an overloaded orthog-
onal drawing (OOD) [4]. In the first case we can assume that
ʓ
has been computed by
some force-directed algorithm (see, e.g., [3]). In the second case we recall that OOD is
a graph visualization paradigm conceived for digraphs [4], which has similarities with
hierarchical and orthogonal drawings. The presence of an edge (
u,v
) is conveyed by an
e
-point (a small circle) placed at the intersection point of the vertical segment passing
through
u
and the horizontal segment passing through
v
. The information in an OOD is
enriched by computing the transitive closure of
G
andbyconveying paths as
p
-points.
Sizing.
This step takes as input
ʓ
and returns a resized drawing
ʓ
R
that matches the
device display resolution and that guarantees all the drawing conventions of the input
drawing
ʓ
.Also,
ʓ
R
should preserve as much as possible some of the drawing original
prominent features. If
ʓ
is straight-line, a technique like the one described in [5] can be
used. If
ʓ
is OOD, it is enough to properly adjust the horizontal and vertical grid unit.
Paging.
In this step the set of edges
E
is partitioned into subsets
E
1
,E
2
,...,E
k
,such
that the subdrawing
p
i
=
ʓ
R
[
E
i
] (1
k
), called
page
, guarantees some desired
property (e.g., planarity). In each subdrawing, the vertices remain fixed in their original
positions as in
ʓ
R
.Thegoal is to distribute the drawing visual complexity along the
pages, which can be explored separately. On the negative side, the user has to face
≤
i
≤
Research supported in part by the MIUR project AMANDA: Algorithmics for MAssive and
Networked DAta, prot. 2012C4E3KT 001.
1
A demo video is available at
http://youtu.be/Toi9lnkbzlo
