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, Bordeaux, France , 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
ID Code:1397

Repository Staff Only: item control page

References

Rome graphs, http://www.graphdrawing.org/download/rome-graphml.tgz

Biedl, T., Bläsius, T., Niedermann, B., Nöllenburg, M., Prutkin, R., Rutter, I.: A versatile ILP/SAT formulation for pathwidth, optimum st-orientation, visibility representation, and other grid-based graph drawing problems. CoRR abs/1308.6778 (2013)

Biere, A., Heule, M., van Maaren, H., Walsh, T. (eds.): Handbook of Satisfiability. IOS Press (2009)

Binucci, C., Didimo, W., Liotta, G., Nonato, M.: Orthogonal drawings of graphs with vertex and edge labels. Comput. Geom. Theory Appl. 32(2), 71–114 (2005)

Bodlaender, H.L., Gilbert, J.R., Hafsteinsson, H., Kloks, T.: Approximating treewidth, pathwidth, frontsize, and shortest elimination tree. J. Algorithms 18(2), 238–255 (1995)

Bodlaender, H.L., Kloks, T.: Efficient and constructive algorithms for the pathwidth and treewidth of graphs. J. Algorithms 21(2), 358–402 (1996)

Brandes, U.: Eager st-ordering. In: Möhring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol. 2461, pp. 247–256. Springer, Heidelberg (2002)

Buchheim, C., Chimani, M., Ebner, D., Gutwenger, C., Jünger, M., Klau, G.W., Mutzel, P., Weiskircher, R.: A branch-and-cut approach to the crossing number problem. Discrete Optimization 5(2), 373–388 (2008)

Chen, D.S., Batson, R.G., Dang, Y.: Applied Integer Programming. Wiley (2010)

Chimani, M., Mutzel, P., Bomze, I.: A new approach to exact crossing minimization. In: Halperin, D., Mehlhorn, K. (eds.) ESA 2008. LNCS, vol. 5193, pp. 284–296. Springer, Heidelberg (2008)

Chimani, M., Zeranski, R.: Upward planarity testing via SAT. In: Didimo, W., Patrignani, M. (eds.) GD 2012. LNCS, vol. 7704, pp. 248–259. Springer, Heidelberg (2013)

Chinn, P.Z., Chvátalova, J., Dewdney, A.K., Gibbs, N.E.: The bandwidth problem for graphs and matrices—a survey. J. Graph Theory 6(3), 223–254 (1982)

Dean, A.M., Evans, W., Gethner, E., Laison, J.D., Safari, M.A., Trotter, W.T.: Bar k-visibility graphs. J. Graph Algorithms Appl. 11(1), 45–59 (2007)

Del Corso, G.M., Manzini, G.: Finding exact solutions to the bandwidth minimization problem. Computing 62(3), 189–203 (1999)

Dujmovic, V., Fellows, M.R., Kitching, M., Liotta, G., McCartin, C., Nishimura, N., Ragde, P., Rosamond, F.A., Whitesides, S., Wood, D.R.: On the parameterized complexity of layered graph drawing. Algorithmica 52(2), 267–292 (2008)

Eén, N., Sörensson, N.: An extensible SAT-solver. In: Giunchiglia, E., Tacchella, A. (eds.) SAT 2003. LNCS, vol. 2919, pp. 502–518. Springer, Heidelberg (2004)

Even, S., Tarjan, R.E.: Computing an st-numbering. Theoret. Comput. Sci. 2(3), 339–344 (1976)

Felsner, S., Liotta, G., Wismath, S.: Straight-line drawings on restricted integer grids in two and three dimensions. J. Graph Algorithms Appl. 7(4), 363–398 (2003)

Gange, G., Stuckey, P.J., Marriott, K.: Optimal k-level planarization and crossing minimization. In: Brandes, U., Cornelsen, S. (eds.) GD 2010. LNCS, vol. 6502, pp. 238–249. Springer, Heidelberg (2011)

Gurobi Optimization, Inc.: Gurobi optimizer reference manual (2013)

Hopcroft, J., Tarjan, R.: Efficient planarity testing. J. ACM 21(4), 549–568 (1974)

Jünger, M., Mutzel, P.: 2-layer straightline crossing minimization: Performance of exact and heuristic algorithms. J. Graph Algorithms Appl. 1(1), 1–25 (1997)

Kratochvíl, J.: A special planar satisfiability problem and a consequence of its NP-completeness. Discrete Appl. Math. 52(3), 233–252 (1994)

Lin, X., Eades, P.: Towards area requirements for drawing hierarchically planar graphs. Theoret. Comput. Sci. 292(3), 679–695 (2003)

Martí, R., Campos, V., Piñana, E.: A branch and bound algorithm for the matrix bandwidth minimization. Europ. J. of Operational Research 186, 513–528 (2008)

Nöllenburg, M., Wolff, A.: Drawing and labeling high-quality metro maps by mixed-integer programming. IEEE TVCG 17(5), 626–641 (2011)

Papamanthou, C., G. Tollis, I.: Applications of parameterized st-orientations. J. Graph Algorithms Appl. 14(2), 337–365 (2010)

Sadasivam, S., Zhang, H.: NP-completeness of st-orientations for plane graphs. Theoret. Comput. Sci. 411(7-9), 995–1003 (2010)

Tamassia, R., Tollis, I.: A unified approach to visibility representations of planar graphs. Discrete Comput. Geom. 1(1), 321–341 (1986)

Wismath, S.K.: Characterizing bar line-of-sight graphs. In: Proc. First Ann. Symp. Comput. Geom., SCG 1985, pp. 147–152. ACM, New York (1985)