Dynamic Bipartite Graph Drawing Problem
Martí R., Martínez-Gavara, A., Sánchez-Oro J., and Duarte A. (2017)
Optsicom project, University of Valencia (Spain)
Problem Description
Drawings of graphs have many applications and they are nowadays well-established tools in computer science in general, and optimization in particular. Project scheduling is one of the many areas in which representation of graphs constitutes an important instrument. The experience shows that the main quality desired for drawings of graphs is readability, and crossing reduction is a fundamental aesthetic criterion to achieve it. Incremental or dynamic graph drawing is an emerging topic in this context, where we seek to preserve the layout of a graph over successive drawings. In this paper, we target the edge crossing reduction in the context of incremental graph drawing. Specifically, we apply a mathematical programming formulation and several heuristic methods based on the tabu search methodology to solve it. In line with the previous paper on this topic, we consider bipartite graphs in our experimentation. The extensive computational experiments with more than 1,000 instances show the superiority of our proposals in both, quality and computing time.
Instances (DBDPLIB)
We employed two sets of instances in our experimentation. The first one contains 120 instances generated according to Martí and Estruch (2001), while the second one has 1000 instances and of instances based on the original number of vertices in each layer, (n1, n2), and the graph 12 was proposed by Stallmann et al. (2001). In line with previous papers, we generated the first set density d in the interval [0.065, 0.175]. Additionally, as in Martí and Estruch (2001), the instances are incremented adding vertices and edges up to pre-established numbers. These numbers are calculated as a percentage δ of the quantities in the original graph (|IVi| = δ|Vi| for each i=1,2, and |IE|=δ|E|. The second set contains 1000 instances obtained with the generator described in Stallmann et al. (2001), which is publicly available. The size of the first layer is in the range [10, 377], while the size of second layer ranges from 10 to 190 nodes. The number of edges is in the range [20, 950]. These instances are bipartite graphs, and we convert them in incremental bipartite graphs by considering a percentage of their nodes as the new nodes added to the original graph. In this way, we kept the structure and density of the instance. In particular, for each original instance we have generated three new instances obtained by selecting as new nodes the 10%, 20%, and 30% percent of the original nodes.
The DBDPLIB contains 1120 instances:
Download DBDP instances (DBDPLIB).
Computational Experience
The computational experiments described in this section were performed to test the effectiveness and efficiency of the procedures discussed above. The previous GRASP method, called prev_GRASP, by Martí and Estruch (2001), and our new procedures were implemented in Java SE 8, and the experiments were conducted on a computer with a 2.8 GHz Intel Core i7 processor with 16 GB of RAM. In particular, we report the results obtained with our constructive method, tabu search, and path relinking post-processing. Additionally, the mathematical programming formulation described in Section 2 was solved with Gurobi