Using ILP/SAT to determine pathwidth, visibility representations, and other grid-based graph drawings

DOI10.1007/978-3-319-03841-4_40zbMATH Open1406.68065arXiv1308.6778OpenAlexW2112136399MaRDI QIDQ2867684FDOQ2867684

Authors: Thomas Bläsius, Benjamin Niedermann, Martin Nöllenburg, Roman Prutkin, Ignaz Rutter, Therese Biedl 

Publication date: 20 December 2013

Published in: Graph Drawing (Search for Journal in Brave)

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 st-orientation, area-minimal (bar-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.

Full work available at URL: https://arxiv.org/abs/1308.6778

Recommendations

• On the path-width of integer linear programming
• EPG-representations with Small Grid-Size
• On the path-width of integer linear programming
• Snapping graph drawings to the grid optimally
• scientific article; zbMATH DE number 1974106

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph representations (geometric and intersection representations, etc.) (05C62)

Cited In (4)

• Art gallery problem with rook and queen vision
• Finding small-width connected path decompositions in polynomial time
• Linear ordering based MIP formulations for the vertex separation or pathwidth problem
• Experimental evaluation of a branch-and-bound algorithm for computing pathwidth and directed pathwidth

This page was built for publication: Using ILP/SAT to determine pathwidth, visibility representations, and other grid-based graph drawings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2867684)