Min-Max Arc Crossing

T. Pastore, A. Martinez-Gavara, A. Napoletano, P. Festa, and R. Martí (2018)
Optsicom project, University of Valencia (Spain)

Problem Description

The crossing minimization problem in hierarchical digraphs has received a lot of attention. Even the problem in bipartite graphs has been extensively studied for more than 40 years, beginning with the Relative Degree Algorithm introduced in Carpano [6]. Early heuristics were based on simple ordering rules, reflecting the goal of researchers and practitioners of quickly obtaining solutions of reasonable quality. However, the field of optimization has recently evolved introducing complex methods, both in exact and heuristic domains. The crossing problem has benefited from these techniques, and advanced solution strategies have been proposed in the last 20 years to solve it.

We focus on a variant of the crossing problem recently introduced in Stallmann (2012). In particular, this author identified some applications in the context of VLSI circuits design in which it is more appropriate to minimize the maximum number of crossings over all edges (min-max) rather than the sum of the edge crossings over all the graph (min-sum). This application motivated the work by Stallman, originally called the bottleneck crossing minimization, where a heuristic algorithm is proposed to minimize the maximum number of crossings among all edges. More recently, Martí et al. (2018) applied a metaheuristic algorithm to solve the problem defined in Stallman’s work, which they called the max-min crossing problem. Remarkably, the solution of the min-max problem is also useful in general graph drawing softwares, where zooming highlights a specific area of the graph where it is then desirable to have a low number of crossings.

State of the Art Methods

Two previous heuristic algorithms were developed to solve this problem:

  • MCE: method based on the sifting principle, which performs passes over the layers of the graph, trying to relocate the endpoints of edges with an elevated number of crossing, until no further improvement can be found. Stallmann (2012)
  • SO: iterated greedy heuristic based on the Strategic Oscillation methodology. This procedure alternates three steps: constructive phase, neighborhood search and destructive phase, in which tries to improve the number of crossing of edges whose cost is close to the maximum (near critical edges). Martí et al. (2018).

Instances

All the instances employed in the experimentation were generated using the generator provided by Stallmann (2012). The benchmark set is made up by a total of 149 networks of heterogeneous size, with graph densities ranging from low values, with a minimum density of 1.5, to high values, with a maximum density of 14.5.

There is 1 folder in the MinMaxGDPlib.zip file: with 60 instances. The file format follows:

The first line has the following fields separed with spaces:

  • n: Integer indicating the total number of vertices in the graph
  • m: Integer indicating the total number of edges in the graph
  • k: Integer indicating the total number of layers in the graph

Starting from the second line, the number of nodes in each layer are reported. The nodes are numbered sequentially. Each of the following lines represent an edge among two adjacent layers of the graph, in the format: starting_node end_node. For example:6 4 2 3 3 1 5 2 4 3 6 3 5

is a graph with six total nodes, divided in two layers of three nodes each. The total number of edges is four, and the vertices in the first layer are labeled as 1 2 3, while the vertices in the second layer are labeled 4 5 6. the connections are between node 1 and node 5, node 2 and node 4, node 3 and 6, and node 3 and 5.

Download Min-Max Arc Crossing Instances (MinMaxGDPlib).

Computational Experience

The computational experiments described in this section were performed to assess the performances of the Tabu Search implementation proposed in this paper. The comparative testing can be divided in a two-round competitive experimentation: in the first round of experiments, we investigate the comparison between CPLEX (v12.8), MCE and our Tabu Search, while solving small-sized instances with low density. In the second round of experiments we undertake the comparison of the three heuristic methods (MCE, SO and Tabu Search), while drawing more complex networks with higher graph densities.

Min-Max Arc Crossing results

References

  • Carpano (1980). Automatic display of hierarchized graphs for computer-aided decision analysis. IEEE Transactions on Systems, Man, and Cybernetics, 10(11):705-715.
  • Martí, R., V. Campos, A. Hoff, and J. Peiró (2018). Heuristics for the min-max arc crossing problem in graphs. Expert Systems with Applications 109, 100-113.
  • Stallmann, M.F. (2012). A heuristic for bottleneck crossing minimization and its performance on general crossing minimization: Hypothesis and experimental study. ACM Journal of Experimental Algorithms, 17(1): 1-30.