Top

Published in:

2015 | OriginalPaper | Chapter

The Book Embedding Problem from a SAT-Solving Perspective

Authors : Michael A. Bekos, Michael Kaufmann, Christian Zielke

Published in: Graph Drawing and Network Visualization

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Drawing Planar Cubic 3-Connected Graphs with Few Segments: Algorithms and Experiments

next chapter Size- and Port-Aware Horizontal Node Coordinate Assignment

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)CrossRef

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

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) CrossRef

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

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)MathSciNetCrossRefMATH

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)MathSciNetCrossRefMATH

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)

10.

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) CrossRef

11.

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)MathSciNetCrossRefMATH

12.

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

13.

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

14.

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) CrossRef

15.

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) CrossRef

16.

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

17.

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

18.

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

19.

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

20.

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)MathSciNetCrossRef

21.

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

22.

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

23.

Malitz, S.: Genus \(g\) graphs have pagenumber \(O(\sqrt{q})\). J. Algorithms 17(1), 85–109 (1994)MathSciNetCrossRefMATH

24.

Malitz, S.: Graphs with \(e\) edges have pagenumber \(O(\sqrt{E})\). J. Algorithms 17(1), 71–84 (1994)MathSciNetCrossRefMATH

25.

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)

26.

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)

27.

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

28.

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

29.

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

30.

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

31.

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) CrossRef

32.

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

33.

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

Title: The Book Embedding Problem from a SAT-Solving Perspective
Authors: Michael A. Bekos
Michael Kaufmann
Christian Zielke
Publisher: Springer International Publishing
Book: Graph Drawing and Network Visualization
Print ISBN: 978-3-319-27260-3

Electronic ISBN: 978-3-319-27261-0

Copyright Year: 2015
DOI: https://doi.org/10.1007/978-3-319-27261-0_11

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner