Theoretical Computer Science / Theoretische Informatik

Institut[e] f(o|ü)r Informati(cs|k), [Universität] Osnabrück [University]

User Tools


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:

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.

research/ucr.txt · Last modified: January 07, 2014 (12:09) by zeranski