Theoretical Computer Science / Theoretische Informatik

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

research:upward

Upward Planarity

Here, you can find the benchmark sets used in our computational study of upward planarity. Detailed descriptions can be found in the paper:

Instances

Rome graphs (Rome) - Rome_all.zip (4.8MB) Leda
North DAGs (North) - att.zip (575KB) GML
biconnected Rome (Rome2) biconnected Rome_bc.zip (1.2MB) GML
biconnected North (North2) biconnected North_bc.zip (351KB) GML
BDD planar bimodal, biconnected BDD.tgz (333KB) GD Toolkit
SP series parallel, biconnected sp_bc.zip (5.7MB) GML
RAND planar bimodal, biconnected Random.zip (1.7MB) GML
Phase Transition - Phase_Transition.zip (64KB) GML

File Formats

In the following, we describe the file formats via small examples, which should suffice for understanding the notation of the downloadable files above.

All examples specify a connected graph on three vertices with two directed edges; the first vertex is source for both.

Leda

Our prototypical file looks like this:

LEDA.GRAPH
void
void
3
|{}|
|{}|
|{}|
2
1 2 0 |{}|
1 3 0 |{}|

The first three lines can be ignored. the forth line (3) gives the number n of vertices. The next n lines then give data for these vertices (labels, positions, etc.). In our files these lines contain only the empty data field encoded by |{}|. The next lines gives the number of edges (2), followed by that many lines specifying the individual edges. Each edge is given by its start (1) and end vertex( e.g., 2), always followed by 0 |{}|.

GML

Our prototypical file looks like this:

Creator "ogdf::GraphIO::writeGML"
graph [
directed 1
node [
id 0
]
node [
id 1
]
node [
id 2
]
edge [
source 0
target 1
]
edge [
source 0
target 2
]
]

Obvisouly, the first line can be ignored.

GD Toolkit

Our prototypical file looks like this:

<UNDISECTION>
<NODELIST>
<NODE>
0
<EDGE> 1 ->
<EDGE> 2 ->
</NODE>
<NODE>
1
<EDGE> 0 <-
</NODE>
<NODE>
2
<EDGE> 0 <-
</NODE>
</NODELIST>
</UNDISECTION>
<DRAWSECTION>
...
</DRAWSECTION> 

The format is XML-like, and rather selfexplanatory from above. Node the symbols following the edge descriptions that specify the edge direction! Everthing within the DRAWSECTION can be ignored.