A survey on book-embedding of planar graphs

Abstract

The book-embedding problem arises in several area, such as very large scale integration (VLSI) design and routing multilayer printed circuit boards (PCBs). It can be used into various practical application fields. A book embedding of a graph G is an embedding of its vertices along the spine of a book, and an embedding of its edges to the pages such that edges embedded on the same page do not intersect. The minimum number of pages in which a graph G can be embedded is called the pagenumber or book-thickness of the graph G. It is an important measure of the quality for book-embedding. It is NP-hard to research the pagenumber of book-embedding for a graph G. This paper summarizes the studies on the book-embedding of planar graphs in recent years.

Keywords

Book embedding / planar graphs / pagenumber

References

[1] Alam M J , Brandenburg F J , Kobourov S G . On the book thickness of 1-planar graphs. 2015, arXiv: 1510.05891

[2] Alam M J , Brandenburg F J , Kobourov S G . Straight-line grid drawings of 3-connected 1-planar graphs. In: Graph Drawing, Lecture Notes in Comput. Sci., Vol. 8242, Cham: Springer, 2013, 83- 94

[3] Alam M J , Bekos M A , Gronemann M , Kaufmann M , Pupyrev S . . Graph-theoretic Concepts in Computer Science (44th International Workshop, WG 2018, Cottbus, Germany), A. Brandest adt, E. Kohler, K. Meer, Eds., LNCS 11159, (2018) 1- 14, Springer, Cham, Switzerland

[4] Alam M J , Bekos M A , Gronemann M , Kaufmann M , Pupyrev S . On dispersable book embeddings. Theoret. Comput. Sci., 2021, 861: 1- 22

[5] Alhashem M , Jourdan G V , Zaguia N . On the book embedding of ordered sets. Ars Combin., 2015, 119: 47- 64

[6] Angelini P , Da Lozzo G , Neuwirth D . Advancements on SEFE and partitioned book embedding problems. Theoret. Comput. Sci., 2015, 575: 71- 89

[7] Atneosen G A . On the Embeddability of Compacta in N-books: Intrinsic and Extrinsic Properties. Ph.D. Thesis, East Lansing, MI: Michigan State University, 1968

[8] Balogh J , Salazar G . Book embeddings of regular graphs. SIAM J. Discrete Math., 2015, 29 (2): 811- 822

[9] Bekos M A , Bruckdorfer T , Kaufmann M , Raftopoulou C . 1-planar graphs have constant book thickness. In: Algorithms—ESA 2015, Lecture Notes in Comput. Sci., Vol. 9294, Heidelberg: Springer, 2015, 130- 141

[10] Bekos M A , Gronemann M , Raftopoulou C N . Two-page book embeddings of 4-planar graphs. Algorithmica, 2016, 75 (1): 158- 185

[11] Bekos M A , Kaufmann M , Zielke C . The book embedding problem from a SAT-solving perspective. In: Graph Drawing and Network Visualization, Lecture Notes in Comput. Sci., Vol. 9411, Cham: Springer, 2015, 125- 138

[12] Bernhart F , Kainen P C . The book thickness of a graph. J. Combin. Theory Ser. B, 1979, 27 (3): 320- 331

[13] Bilski T . Optimum embedding of complete graphs in books. Discrete Math., 1998, 182 (1/2/3): 21- 28

[14] Buss J F , Shor P W . On the pagenumber of planar graphs. In: Proceedings of the 16th Annual ACM Symposium on Theory of Computing (STOC ’84), New York, NY: ACM, 1984, 98- 100

[15] Chen C . Any maximal planar graph with only one separating triangle is hamiltonian. J. Comb. Opim., 2003, 7 (1): 79- 86

[16] Chiba N , Nishizeki T . The hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs. J. Algorithms, 1989, 10 (2): 187- 211

[17] 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 Methods, 1987, 8 (1): 33- 58

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

[19] Endo T . The pagenumber of toroidal graphs is at most seven. Discrete Math., 1997, 175 (1/2/3): 87- 96

[20] Enomoto H , Miyauchi M S . Embedding graphs into a three page book with O(M log N) crossings of edges over the spine. SIAM J. Discrete Math., 1999, 12 (3): 337- 341

[21] Enomoto H , Miyauchi M S , Ota K . Lower bounds for the number of edge-crossings over the spine in a topological book embedding of a graph. Discrete Appl. Math., 1999, 92 (2/3): 149- 155

[22] Enomoto H , Nakamigawa T , Ota K . On the pagenumber of complete bipartite graphs. J. Combin. Theory Ser. B, 1997, 71 (1): 111- 120

[23] Even S , Itai A . Queues, stacks, and graphs. In: Theory of Machines and Computations (Proc. Internat. Sympos., Technion, Haifa, 1971), New York: Academic Press, 1971, 71- 86

[24] Ewald G . Hamiltonian circuits in simplicial complexes. Geometriae Dedicata, 1973, 2: 115- 125

[25] Fang J F , Lai K C . Embedding the incomplete hypercube in books. Inform. Process. Lett., 2005, 96 (1): 1- 6

[26] Games R A . Optimal book embeddings of the FFT, benes, and barrel shifter networks. Algorithmica, 1986, 1 (1): 233- 250

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

[28] Garey M R , Johnson D S , Miller G L , Papadimitriou C H . The complexity of coloring circular arcs and chords. SIAM J. Algebraic Discrete Methods, 1980, 1 (2): 216- 227

[29] Grigoriev A , Bodlaender H L . Algorithms for graphs embeddable with few crossings per edge. Algorithmica, 2007, 49 (1): 1- 11

[30] Guan X X . Book-embedding of Planar Graphs. Master Thesis, Taiyuan: Taiyuan University of Technology, 2019 (in Chinese)

[31] Guan X X , Yang W H . Embedding planar 5-graphs in three pages. Discrete Appl. Math., 2019, 282: 108- 121

[32] Hasunuma T , Shibata Y . Embedding de Bruijn, Kautz and shuffle-exchange networks in books. Discrete Appl. Math., 1997, 78 (1/2/3): 103- 116

[33] Heath L S . Embedding planar graphs in seven pages. In: 25th Annual Symposium on Foundations of Computer Science, New York: IEEE, 1984, 74- 89

[34] Heath L S . Algorithms for Embedding Graphs in Books. Ph.D. Thesis, Chapel Hill, NC: University of North Carolina, 1985

[35] Heath L S , Istrail S . The pagenumber of genus g graphs is O(g). J. Assoc. Comput. Mach., 1992, 39 (3): 479- 501

[36] Helden G . Each maximal planar graph with exactly two separating triangles is hamiltonian. Discret. Appl. Mach., 2007, 155 (14): 1833- 1836

[37] Hoffmann M , Klemz B . Triconnected planar graphs of maximum degree five are subhamiltonian. In: 27th Annual European Symposium on Algorithms (ESA 2019) (Bender, M.A., Svensson, O. and Herman, G. eds.), Leibniz International Proceedings in Informatics (LIPIcs), Vol. 144, Dagstuhl: Schloss Dagstuhl—Leibniz-Zentrum für Informatik, 2019, Article 58, 14 pp

[38] Hwang F K . A survey on multi-loop networks. Theoret. Comput. Sci., 2003, 299 (1/2/3): 107- 121

[39] Istrail S . An algorithm for embedding planar graphs in six pages. An. Ştiinţ. Univ. Al. I. Cuza Iaşi Secţ. I a Mat., 1988, 34 (4): 329- 341

[40] Joslin S S , Kainen P C , Overbay S . On dispersability of some cycle products. Missouri J. Math. Sci., in press, 2021

[41] Kainen P C . Some recent results in topological graph theory. In: Graphs and Combinatorics. Lecture Notes in Math., Vol. 406, Berlin: Springer, 1974, 76- 108

[42] Kainen P C . Complexity of products of even cycles. Bull. Inst. Combinatorics and Its Applications, 2011, 62: 95- 102

[43] Kainen P C , Overbay S . Extension of a theorem of Whitney. Appl. Math. Lett., 2007, 20: 835- 837

[44] Kainen P C , Overbay S . Cubic planar bipartite graphs are dispersable. arXiv: 2107. 4728v1

[45] Kainen P C , Overbay S . On matching book thickness. in preparation

[46] Kapoor N , Russell M , Stojmenovic I , Zomaya A Y . A genetic algorithm for finding the pagenumber of interconnection networks. J. Parallel Distrib. Comput., 2002, 62 (2): 267- 283

[47] Kobourov S G , Liotta G , Montecchiani F . An annotated bibliography on 1-planarity. Computer Science Review 25, 2017, 49- 67

[48] Konoe M , Hagiwara K , Tokura N . On the pagenumber of hypercubes and cube-connected cycles. IEICE Trans., 1988, J71-D (3): 490- 500 (in Japanese)

[49] Korzhik V P , Mohar B . Minimal obstructions for 1-immersions and hardness of 1-planarity testing. J. Graph Theory, 2013, 72 (1): 30- 71

[50] Kwiatkowska A B . On page number of N-free posets. In: Fifth Cracow Conference on Graph Theory USTRON ’06, Electron. Notes Discrete Math., Vol. 24, Amsterdam: Elsevier Sci. B. V., 2006, 243- 249

[51] Li X L . Book Embedding of Graphs. Ph.D. Thesis, Zhengzhou: Zhengzhou University, 2002, 72 (1): 243- 249

[52] Malitz S M . Graphs with E edges have pagenumber O(E). J. Algorithms, 1994, 17 (1): 71- 84

[53] Malitz S M . Genus g graphs have pagenumber O(g). J. Algorithms, 1994, 17: 85- 109

[54] Mitchel S L . Linear algorithms to recognize outerplanar and maximal outerplanar graphs. Inform. Process. Lett., 1979, 9 (5): 224- 232

[55] Moran S , Wolfstahl Y . One-page book embedding under vertex-neighborhood constraints. SIAM J. Discrete Math., 1990, 3 (3): 376- 390

[56] Muder D J , Weaver M L , West D B . Pagenumber of complete bipartite graphs. J. Graph Theory, 1988, 12 (4): 469- 489

[57] Nakamoto A , Nozawa T . Book embedding of locally planar graphs on orientable surfaces. Discrete Math., 2016, 339 (11): 2672- 2679

[58] Nakamoto A , Ozeki K . Book embedding of toroidal bipartite graphs. SIAM J. Discrete Math., 2012, 26 (2): 661- 669

[59] Nowakowski R , Parker A . Ordered sets, pagenumbers and planarity. Order, 1989, 6 (3): 209- 218

[60] Ollmann L T . On the book thicknesses of various graphs. In: Proceedings of the 4th Southeastern Conference on Combinatorics. Graph Theory and Computing, Congressus Numerantium, Vol. VIII, Winnipeg, Man.: Utilitas Mathematica Publishing Inc., 1973 459

[61] Overbay S . Generalized Book Embeddings. Ph. D. Dissertation, Colorado State University, Fort Collins, CO, 1998

[62] Pach J , Tóth G . Graphs drawn with few crossings per edge. Combinatorica, 1997, 17 (3): 427- 439

[63] Pupyrev S . Private communication

[64] Pupyrev S . Book Embeddings of Graph Products. arXiv: 2007.15102v1

[65] Ringel G . Map Color Theorem. Die Grundlehren der mathematischen Wissenschaften, Band 209, New York: Springer-Verlag, 1974

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

[67] Sanders D P . The Diogenes approach to testable fault-tolerant arrays of processors. J. Graph Theory., 1997, 24 (4): 341- 345

[68] Shahrokhi F , Shi W P . On crossing sets, disjoint sets, and pagenumber. J. Algorithm, 2000, 34 (1): 40- 53

[69] Shao Z , Liu Y , Li Z . Matching book embedding of the Cartesian product of a complete graph and a cycle. arXiv: 2002.00309v1

[70] Shao Z , Liu Y , Li Z . Matching book thickness of Halin graphs. arXiv: 2008.13331v1

[71] So H C . Some theoretical results on the routing of multilayer printed wiring boards. In: Proc. IEEE Symp. on Circuits and Systems, New York: IEEE, 1974, 296- 303

[72] Sperfeld K . On the page number of complete odd-partite graphs. Discrete Math., 2013, 313 (17): 1689- 1696

[73] Swaminathan R P , Giraraj D , Bhatia D K . The pagenumber of the class of bandwidth-k graphs is k − 1. Inform. Process. Lett., 1995, 55 (2): 71- 74

[74] Sysło M M . Characterizations of outerplanar graphs. Discrete Math., 1979, 26 (1): 47- 53

[75] Tanaka Y , Shibata Y . On the pagenumber of trivalent Cayley graphs. Discrete Appl. Math., 2006, 154 (8): 1279- 1292

[76] Tarjan R . Sorting using networks of queues and stacks. J. Assoc. Comput. Mach., 1972, 19: 341- 346

[77] Thomassen C . Rectilinear drawings of graphs. J. Graph Theory, 1988, 12 (3): 335- 341

[78] Thompson C D . A Complexity Theory for VLSI. Ph.D. Thesis, Pittsburgh, PA: Carnegie Mellon University, 1980

[79] Tutte W T . A theorem on planar graphs. Trans. Amer. Math. Soc., 1956, 82: 99- 116

[80] Wang M . Some results for embedding grid graphs in books. J. Zhengzhou Univ. (Nat. Sci. Ed.), 1997, 29 (2): 31- 34 (in Chinese)

[81] Whitney H . A theorem on graphs. Ann. Math. 1931, 32: 378- 390

[82] Wigderson A . The complexity of the Hamiltonian circuit problem for maximal planar graphs. Technical Report 298, Department of EECS, Princeton University, February (1982)

[83] Wood D R . Degree constrained book embeddings. J. Algorithms, 2002, 45 (2): 144- 154

[84] Yang W H , Meng J X . Embedding connected double-loop networks with even cardinality in books. Appl. Math. Lett., 2009, 22 (9): 1458- 1461

[85] Yannakakis M . Four pages are necessary and sufficient for planar graphs. In: Proceedings of the 18th Annual ACM Symposium on Theory of Computing (STOC ’86), New York, NY: ACM, 1986, 104- 108

[86] Yannakakis M . Embedding planar graphs in four pages. J. Comput. System Sci., 1989, 38 (1): 36- 67

[87] Yannakakis M . Planar Graphs that Need Four Pages. J. Combin. Theory Ser. B, 2020, 145: 241- 263

[88] Zhang Y M , Chen G L . The results of embedding several graphs in books. Chinese J. Computer, 1993, 16 (7): 509- 518 (in Chinese)

[89] Zhao B . The Book Embedding of Some Graphs. Ph.D. Thesis, Urumqi: Xinjiang University, 2016 (in Chinese)

[90] Zhao B , Chen L H , Zhang Y P , Tian Y Z , Meng J X . On the page number of triple-loop networks with even cardinality. Ars Combin., 2016, 124: 257- 266

[91] Zhao B , Meng J X . Embedding connected double-loop networks with odd cardinality in books. J. Xinjiang Univ. (Nat. Sci. Ed.), 2011, 28 (2): 152- 155

[92] Zhao B , Tian Y Z , Meng J X . Embedding semistrong product of paths and cycles in books. J. Nat. Sci. Hunan Norm. Univ., 2015, 38 (6): 73- 77

[93] Zhao B , Tian Y Z , Meng J X . On the page number of lexicographic product of paths and cycles in books. J. Xinjiang Univ. (Nat. Sci. Ed.), 2016, 33 (1): 1- 5

[94] Zhao B , Xiong W , Tian Y Z , Meng J X . Embedding generalized Petersen graph in books. Chin. Ann. Math. Ser. B, 2016, 37 (3): 385- 394

RIGHTS & PERMISSIONS

Higher Education Press