Using ILP/SAT to Determine Pathwidth, Visibility Representations, and other Grid-Based Graph Drawings

Biedl, Therese and Bläsius, Thomas and Niedermann, Benjamin and Nöllenburg, Martin and Prutkin, Roman and Rutter, Ignaz (2013) Using ILP/SAT to Determine Pathwidth, Visibility Representations, and other Grid-Based Graph Drawings. In: 21st International Symposium, GD 2013, September 23-25, 2013 , pp. 460-471(Official URL: http://dx.doi.org/10.1007/978-3-319-03841-4_40).

Full text not available from this repository.

Abstract

We present a simple and versatile formulation of grid-based graph representation problems as an integer linear program (ILP) and a corresponding SAT instance. In a grid-based representation vertices and edges correspond to axis-parallel boxes on an underlying integer grid; boxes can be further constrained in their shapes and interactions by additional problem-specific constraints. We describe a general d-dimensional model for grid representation problems. This model can be used to solve a variety of NP-hard graph problems, including pathwidth, bandwidth, optimum \textit{st}-orientation, area-minimal (bar-\textit{k}) visibility representation, boxicity-k graphs and others. We implemented SAT-models for all of the above problems and evaluated them on the Rome graphs collection. The experiments show that our model successfully solves NP-hard problems within few minutes on small to medium-size Rome graphs.

Item Type:	Conference Paper
Classifications:	S Software and Systems > S.001 General
URI:	http://gdea.informatik.uni-koeln.de/id/eprint/1397

Actions (login required)

View Item