PIGRA– A Tool for Pixelated Graph Representations - Graph Drawing - page 512

P I G RA - A Tool for Pixelated Graph Representations

Thomas Blasius, Fabian Klute, Benjamin Niedermann, and Martin N ollenburg

Karlsruhe Institute of Technology(KIT),Germany

At GD 2013 Biedl et al. presented a simple and versatile formulation of grid-based
graph representation problems as integer linear programs (ILPs) and corresponding
S AT -instances [1]. In a grid-based representation each vertex and each edgeofagraph is
represented by a set of grid cells, which we also call pixels . Biedl et al. described a gen-
eral ILP model, where each object (vertex or edge) corresponds to a set of variables that
determine which pixels represent the object. They introduced constraints that restrict
the shapes of objects (e.g., requiring the pixels of a vertex to form a 2D box) and how
the representations of different objects can intersect. In this way, one can solve a variety
of NP-hard graph problems, including pathwidth, bandwidth, optimum st -orientation,
area-minimal (bar- k ) visibility representation, boxicity- k graphs and others. For exam-
ple, in a grid-based drawing of a visibility representation, each vertex is represented by
a horizontal box of height 1 and each edge is represented by a vertical box of width 1.
Moreover, two boxes overlap if and only if they represent a vertex and an incident edge.
Biedl et al. [1] implemented and evaluated the ILP-models for the above problems.
The experiments showed that their models successfully solve NP-hard problems within
few minutes on small to medium-size graphs. They further provided their C++ imple-
mentation as the framework G D S AT 1 , which can be freely downloaded and adapted.
With G D S AT it requires little effort to solve problems that are already modeled
within G D S AT for a given graph. However, adapting the models to solve different grid-
based graph drawing problems requires deeper insights and adaptions. Moreover, there
is no graphical outputoftheresult. Hence, it is not an easy-to-use tool for tasks like
running initial experiments to explore new grid-based graph drawing problems.
To make the framework of Biedl et al. [1] more widely accessible and usefultothe
community, we developed the GUI-based tool P I G RA ( pi xelated gra phs) that allows
to easily combine pre-defined general constraints in order to model the above men-
tioned problems as well as other grid-based layout problems. Additionally, in case the
pre-defined constraints are not sufficient, the user may adapt existing or define new
constraints using the simple, mathematically-oriented language PGL ( p ixelated g raphs
l anguage), which we have introduced for this purpose.
In P I G RA the typical workflow consists of the following three steps; see Fig.1.
1. The user defines the problem as a generic ILP-formulation in P I G RA , using com-
binations of pre-defined and custom constraints formulated in PGL.
2. P I G RA instantiates the ILP-formulation for a user-specified graph and solves it with
G UROBI 2 (an automatic conversion to an equivalent S AT -instance is planned).
3. The resultinggrid-based representation is graphically displayed and can be interac-
tively explored.

1

i11www.iti.kit.edu/gdsat - The name G D S AT comes from the fact that solving an
equivalent S AT -instance performs better than solving the ILP itself.
2 www.gurobi.com