Biedl, Therese C.; Bläsius, Thomas; Niedermann, Benjamin; Nöllenburg, Martin; Prutkin, Roman; Rutter, Ignaz Using ILP/SAT to Determine Pathwidth, Visibility Representations, and other Grid-Based Graph DrawingsGraph Drawing (GD) 2013: 460–471
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.
Bläsius, Thomas; Karrer, Annette; Rutter, Ignaz Simultaneous Embedding: Edge Orderings, Relative Positions, CutverticesGraph Drawing (GD) 2013: 220–231
A simultaneous embedding (with fixed edges) of two graphs \(G^1\) and \(G^2\) with common graph \(G = G^1 \cap G^2\) is a pair of planar drawings of \(G^1\) and \(G^2\) that coincide on \(G\). It is an open question whether there is a polynomial-time algorithm that decides whether two graphs admit a simultaneous embedding (problem Sefe). In this paper, we present two results. First, a set of three linear-time preprocessing algorithms that remove certain substructures from a given Sefe instance, producing a set of equivalent Sefe instances without such substructures. The structures we can remove are (1) cutvertices of the union graph \(G^{\cup} = G ^1 \cup G^2\) , (2) most separating pairs of \(G^{\cup}\), and (3) connected components of \(G\) that are biconnected but not a cycle. Second, we give an \(O(n^3)\)-time algorithm solving Sefe for instances with the following restriction. Let \(u\) be a pole of a \(P\)-node \(\mu\) in the SPQR-tree of a block of \(G^1\) or \(G^2\) . Then at most three virtual edges of \(\mu\) may contain common edges incident to \(u\). All algorithms extend to the sunflower case, i.e., to the case of more than three graphs pairwise intersecting in the same common graph.