[Back]

M. Nöllenburg, A. Villedieu, J. Wulms:
"Layered Area-Proportional Rectangle Contact Representations";
Talk: International Symposium on Graph Drawing and Network Visualization (GD), Tübingen, Germany; 2021-09-14 - 2021-09-17; in: "International Symposium on Graph Drawing and Network Visualization-GD2021", LNCS / Springer, 12868 (2021), ISBN: 978-3-030-92930-5; 318 - 326.

We investigate two optimization problems on area-proportional
rectangle contact representations for layered, embedded planar
graphs. The vertices are represented as interior-disjoint unit-height rectangles
of prescribed widths, grouped in one row per layer, and each edge
is ideally realized as a rectangle contact of positive length. Such rectangle
contact representations find applications in semantic word or tag cloud
visualizations, where a collection of words is displayed such that pairs
of semantically related words are close to each other. In this paper, we
want to maximize the number of realized rectangle contacts or minimize
the overall area of the rectangle contact representation, while avoiding
any false adjacencies. We present a network flow model for area minimization,
a linear-time algorithm for contact maximization of two-layer
graphs, and an ILP model for maximizing contacts of k-layer graphs.

http://dx.doi.org/10.1007/978-3-030-92931-2_23