Nöllenburg, M., Villedieu, A., & Wulms, J. (2021). Layered Area-Proportional Rectangle Contact Representations. In Graph Drawing and Network Visualization. GD 2021 (pp. 318–326). Springer. https://doi.org/10.1007/978-3-030-92931-2_23
E192-01 - Forschungsbereich Algorithms and Complexity
-
Published in:
Graph Drawing and Network Visualization. GD 2021
-
Volume:
12868
-
Date (published):
2021
-
Event name:
29th International Symposium on Graph Drawing and Network Visualization (GD 2021)
-
Event date:
14-Sep-2021 - 17-Sep-2021
-
Event place:
Tübingen, Germany
-
Number of Pages:
9
-
Publisher:
Springer, Cham
-
Peer reviewed:
Yes
-
Abstract:
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.
