Information Technology Reference
In-Depth Information
Fig. 1.
Screenshots of a typical workflow in P
I
G
RA
using the example of bar-
k
visibility represen-
tations. Model formulation using a combination of pre-defined constraints and custom constraints
expressed in PGL (left). Graphical outputoftheILP solution for a small example graph (right).
P
I
G
RA
provides a variety of pre-defined ILP-constraints that are usefultoformulate
many custom grid-based graph drawing problems and can simply be selected by ticking
the corresponding check-boxes. Among others, the following constraints are available:
(a)
vertices or edges are represented by boxes,
(b)
boxes have a certain height or width,
(c)
certain types of boxes may not overlap,
(d)
boxes of edges overlap exactly the boxes
of their incident vertices. Additional constraints on shapes and intersections can be
specified directly in P
I
G
RA
usingPGL. For example, vertices could be modeled as
the union of two boxes with non-empty intersection, including the special case of L-
shapes. Or a constraint could be added so that each vertex box may only intersect a
single incident edge, which models selecting a set of matching edges. In summary, the
main features of P
I
G
RA
are:
-
A macro system with pre-defined ILP-constraints for grid-based graph layouts.
-
The simple, mathematically-oriented language PGL providing the capability to for-
mulate ILP constraints with low overhead.
-
A simple editor for writing constraints in PGL. Since all pre-defined constraints
are also written in PGL, the user may adapt those constraints.
-
A well-structured graphical user interface for presenting the result of the ILP as
grid-based graph drawing.
-
Support of GML-format for loadinggraphs (we use OGDF
3
to parse GML-files).
-
Implemented in C++ and soon available for download
4
under the GPL.
References
1. Biedl, T., Blasius, T., Niedermann, B., N ollenburg,M.,Prutkin, R., Rutter, I.: Using ILP/SAT
to determine pathwidth, visibility representations, and other grid-based graph drawings. In:
Wismath, S., Wolff, A. (eds.) GD 2013. LNCS, vol. 8242, pp. 460-471. Springer, Heidelberg
(2013)
3
