Models and solution approaches for the optimal assignment of vertices to layers in a hierarchical graph
J. Sánchez-Oro, A. Martinez-Gavara, M. Laguna, and R. Martí
Data visualization tools and technologies have become essential elements in data analytics. As companies subscribe to the notion of making data-driven decisions, visualization enables the transformation of data into insightful and actionable information. Within this framework, hierarchical graphs provide a mechanism to visualize complex relationships extracted from large data sets. Hierarchical (or layered) graphs are drawn in three stages: 1) assigning vertices to layers, 2) permuting the vertices in each layer, and 3) placing each vertex in a specific coordinate. While the graph drawing literature has focused on the second stage, we are interested in the first. We formulate it as an optimization problem, for which we propose various models and solution approaches. Our computational experiments show the merit of applying the proposed optimization techniques to the problem of assigning vertices to layers in a hierarchical graph.