Upward Crossing Minimization
Here, you can find the benchmark sets used in our study of upward crossing minimization. Detailed descriptions and results can be found in the paper:
- M. Chimani, R. Zeranski. An Exact Approach To Upward Crossing Minimization. SIAM Meeting on Algorithm Engineering & Experiments (ALENEX'14), Portland, 2014. to appear.
Instances
| Name | Properties | # | Link |
|---|---|---|---|
| Rome graphs (Rome) | non upward planar | 3117 | rome_nonupward.zip (1.8MB) |
| Rome graphs (Rome) upward | upward planar | 3022 | rome_upward.zip (1.3MB) |
| North DAGs (North) | non upward planar | 464 | att_nonupward.zip (284KB) |
| RAND1 | planar, biconnected, non upward planar | 1152 | rand1_nonupward.zip (1.0MB) |
| RAND1 upward | biconnected, upward planar | 1152 | rand1_upward.zip (996KBMB) |
| RAND2 | non upward planar | 500 | rand2_nonupward.zip (274KB) |
Description
Recognizing upward planar/non-upward planar instances: We used the FPSS-approach presented in Chimani M., Zeranski, R.: Upward Planarity: A Computational Study to recognize upward planar instances (resp. non-upward planar instances)
Construction of RAND1 instances: We start with a triangle graph with 3 vertices and 3 edges. There are two possible operations:
- edge-subdivision: Choose any edge by random and subdivide it (by introducing a new vertex). This operation introduces exactly one new vertex.
- face-split: Choose any face with more than 3 incident vertices by random and split the face by introducing a new edge among 2 random vertices of the face. This operation introduces exactly one new edge.
If the graph has at least one face with more than 3 vertices we will choose per random whether we perform an edge-subdivision or a face-split, otherwise we perform an edge-subdivision. Repeat this step until the graph has the requested number of vertices (resp. density). After that, the edges of the graph will be oriented upward, i.e., the index of the source-vertex is smaller than the index of the target-vertex. Note, that the graph is upward planar (and biconnected). To generate possibly non-upward planar instances we invert the orientations of a fixed percentage of edges by random, preserving acyclicity. The implementation of this graph-generator can be found within the OGDF.
The graphs were conctructed with |V| = 20,30,…,100 vertices; density |E|/|V| = 1.2,1.4,…,2.6; and % = 1,2,3,4. For each choice of the parameters we generated 4 graphs.
Construction of RAND2 instances: We are starting with n isolated vertices. After that, we introduce m edges uniformly by random, preventing multi-edges and preserving acyclicity. Certainly, the contructed graph has very many crossings. Hence we want to examine the performance of the known heurtsics and our approach seems not to be able to solve instances with a huge amount of crossings, we want to minimize the number of crossings of the generated graph. Therefore, we discard graphs with too many crossings by computing an upper bound using the UPL-heuristic. If the heuritic needs more than 20 crossings we discard the graph. Nevertheless, if 50 graphs were discarded using the actual crossing limit, we increase this limit by 5.
The graphs were constructed with |V| = 10,20,…,50 vertices and density |E|/|V| = 1.2,1.4,…,2.0. For each choice of the parameters we generated 20 graphs.