The Book Embedding Problem from a SAT-Solving Perspective

Bekos, Michael A. and Kaufmann, Michael and Zielke, Christian (2015) The Book Embedding Problem from a SAT-Solving Perspective. In: Graph Drawing and Network Visualization: 23rd International Symposium, GD 2015, September 24-26, 2015, Los Angeles, CA, USA , pp. 125-138 (Official URL: http://dx.doi.org/10.1007/978-3-319-27261-0_11).

Full text not available from this repository.

Abstract

In a book embedding, the vertices of a graph are placed on the spine of a book and the edges are assigned to pages, so that edges of the same page do not cross. In this paper, we approach the problem of determining whether a graph can be embedded in a book of a certain number of pages from a different perspective: We propose a simple and quite intuitive SAT formulation, which is robust enough to solve non-trivial instances of the problem in reasonable time. As a byproduct, we show a lower bound of 4 on the page number of 1-planar graphs.

Item Type:Conference Paper
Classifications:G Algorithms and Complexity > G.490 Embeddings
M Methods > M.999 Others
P Styles > P.999 Others
ID Code:1483

Repository Staff Only: item control page

References

Bekos, M., Gronemann, M., Raftopoulou, C.N.: Two-page book embeddings of 4-planar graphs. In: STACS, vol. 25, pp. 137–148. LIPIcs, Schloss Dagstuhl (2014)

Bekos, M.A., Bruckdorfer, T., Kaufmann, M., Raftopoulou, C.: 1-planar graphs have constant book thickness. In: Bansal, N., Finocchi, I. (eds.) ESA 2015. LNCS, vol. 9294, pp. 130–141. Springer, Heidelberg (2015)

Bernhart, F., Kainen, P.: The book thickness of a graph. Comb. Theory 27(3), 320–331 (1979)

Biedl, T., Bläsius, T., Niedermann, B., Nöllenburg, M., Prutkin, R., Rutter, I.: Using ILP/SAT to determine pathwidth, visibility representations, and other grid-based graph drawings. In: Wismath, S., Wolff, A. (eds.) GD 2013. LNCS, vol. 8242, pp. 460–471. Springer, Heidelberg (2013)

Bilski, T.: Embedding graphs in books: a survey. IEEE Proc. Comput. Digit. Tech. 139(2), 134–138 (1992)

Blankenship, R.: Book embeddings of graphs. Ph.D. thesis, Louisiana State University (2003)

Bodendiek, R., Schumacher, H., Wagner, K.: Über 1-optimale graphen. Math. Nachr. 117(1), 323–339 (1984)

Brinkmann, G., Greenberg, S., Greenhill, C.S., McKay, B.D., Thomas, R., Wollan, P.: Generation of simple quadrangulations of the sphere. Discrete Math. 305(1–3), 33–54 (2005)

Cheeseman, P., Kanefsky, B., Taylor, W.M.: Where the really hard problems are. In: Mylopoulos, J., Reiter, R. (eds.) AI, pp. 331–340. Morgan Kaufmann (1991)

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)

Chung, F.R.K., Leighton, F.T., Rosenberg, A.L.: Embedding graphs in books: a layout problem with applications to VLSI design. SIAM J. Algebraic Discrete Method 8(1), 33–58 (1987)

Cornuéjols, G., Naddef, D., Pulleyblank, W.: Halin graphs and the travelling salesman problem. Math. Programm. 26(3), 287–294 (1983)

Dujmović, V., Wood, D.: Graph treewidth and geometric thickness parameters. Discrete Comput. Geom. 37(4), 641–670 (2007)

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)

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)

Ganley, J.L., Heath, L.S.: The pagenumber of kk-trees is O(k)O(k). Discrete Appl. Math. 109(3), 215–221 (2001)

Goldner, A., Harary, F.: Note on a smallest nonhamiltonian maximal planar graph. Bull. Malays. Math. Sci. Soc. 1(6), 41–42 (1975)

Heath, L.: Embedding planar graphs in seven pages. In: FOCS, pp. 74–83. IEEE Computer Society (1984)

Heath, L.: Algorithms for embedding graphs in books. Ph.D. thesis, University of N. Carolina (1985)

Heath, L.S., Leighton, F.T., Rosenberg, A.L.: Comparing queues and stacks as machines for laying out graphs. SIAM J. Discrete Math. 3(5), 398–412 (1992)

Kainen, P.C., Overbay, S.: Extension of a theorem of Whitney. Appl. Math. Lett. 20(7), 835–837 (2007)

Kottler, S.: Description of the SApperloT, SArTagnan and MoUsSaka solvers for the SAT-competition 2011 (2011)

Malitz, S.: Genus gg graphs have pagenumber O(q‾√)O(q). J. Algorithms 17(1), 85–109 (1994)

Malitz, S.: Graphs with ee edges have pagenumber O(E‾‾√)O(E). J. Algorithms 17(1), 71–84 (1994)

Nishizeki, T., Chiba, N.: Hamiltonian cycles. In: Planar Graphs: Theory and Algorithms, chap. 10, pp. 171–184. Dover Books on Mathematics, Courier Dover Publications (2008)

Ollmann, T.: On the book thicknesses of various graphs. In: Hoffman, F., Levow, R., Thomas, R. (eds.) Southeastern Conference on Combinatorics, Graph Theory and Computing. Congressus Numerantium, vol. VIII, p. 459 (1973)

Plaisted, D.A., Greenbaum, S.: A structure-preserving clause form translation. J. Symbolic Comput. 2(3), 293–304 (1986)

Rosenberg, A.L.: The Diogenes approach to testable fault-tolerant arrays of processors. IEEE Trans. Comput. C–32(10), 902–910 (1983)

Suzuki, Y.: Optimal 1-planar graphs which triangulate other surfaces. Discrete Math. 310(1), 6–11 (2010)

Tarjan, R.: Sorting using networks of queues and stacks. J. ACM 19(2), 341–346 (1972)

Velev, M.N., Gao, P.: Efficient SAT techniques for relative encoding of permutations with constraints. In: Nicholson, A., Li, X. (eds.) AI 2009. LNCS, vol. 5866, pp. 517–527. Springer, Heidelberg (2009)

Wigderson, A.: The complexity of the Hamiltonian circuit problem for maximal planar graphs. Technical report TR-298, EECS Department, Princeton University (1982)

Yannakakis, M.: Embedding planar graphs in four pages. J. Comput. Syst. Sci. C–38(1), 36–67 (1989)