Please wait a minute...
Shopping Cart Email List Chinese
Advanced Search Fig/Tab
Frontiers of Mathematics in China

ISSN 1673-3452

ISSN 1673-3576(Online)

CN 11-5739/O1

Postal Subscription Code 80-964

2018 Impact Factor: 0.565

Featured Articles  |  Most Downloaded  |  Most Reading
Online Submission Subscribe to Our RSS Content Feed
Front. Math. China    2022, Vol. 17 Issue (2) : 255-273    https://doi.org/10.1007/s11464-022-1010-5
SURVEY ARTICLE
A survey on book-embedding of planar graphs
Xiaxia GUAN1(), Chuxiong WU1, Weihua YANG1, Jixiang MENG2
1. College of Mathematics, Taiyuan University of Technology, Taiyuan 030024, China
2. College of Mathematics and System Science, Xinjiang University, Urumqi 830046, China
 Download: PDF(351 KB)  
 Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks
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     
Corresponding Author(s): Xiaxia GUAN   
Issue Date: 23 May 2022
 Cite this article:   
Xiaxia GUAN,Chuxiong WU,Weihua YANG, et al. A survey on book-embedding of planar graphs[J]. Front. Math. China, 2022, 17(2): 255-273.
 URL:  
https://academic.hep.com.cn/fmc/EN/10.1007/s11464-022-1010-5
https://academic.hep.com.cn/fmc/EN/Y2022/V17/I2/255
1 M J Alam , F J Brandenburg , S G Kobourov . On the book thickness of 1-planar graphs. 2015, arXiv: 1510.05891
2 M J Alam , F J Brandenburg , S G Kobourov . 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 M J Alam , M A Bekos , M Gronemann , M Kaufmann , S Pupyrev . . 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 M J Alam , M A Bekos , M Gronemann , M Kaufmann , S Pupyrev . On dispersable book embeddings. Theoret. Comput. Sci., 2021, 861: 1- 22
https://doi.org/10.1016/j.tcs.2021.01.035
5 M Alhashem , G V Jourdan , N Zaguia . On the book embedding of ordered sets. Ars Combin., 2015, 119: 47- 64
6 P Angelini , Lozzo G Da , D Neuwirth . Advancements on SEFE and partitioned book embedding problems. Theoret. Comput. Sci., 2015, 575: 71- 89
https://doi.org/10.1016/j.tcs.2014.11.016
7 G A Atneosen . On the Embeddability of Compacta in N-books: Intrinsic and Extrinsic Properties. Ph.D. Thesis, East Lansing, MI: Michigan State University, 1968
8 J Balogh , G Salazar . Book embeddings of regular graphs. SIAM J. Discrete Math., 2015, 29 (2): 811- 822
https://doi.org/10.1137/140961183
9 M A Bekos , T Bruckdorfer , M Kaufmann , C Raftopoulou . 1-planar graphs have constant book thickness. In: Algorithms—ESA 2015, Lecture Notes in Comput. Sci., Vol. 9294, Heidelberg: Springer, 2015, 130- 141
10 M A Bekos , M Gronemann , C N Raftopoulou . Two-page book embeddings of 4-planar graphs. Algorithmica, 2016, 75 (1): 158- 185
https://doi.org/10.1007/s00453-015-0016-8
11 M A Bekos , M Kaufmann , C Zielke . 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 F Bernhart , P C Kainen . The book thickness of a graph. J. Combin. Theory Ser. B, 1979, 27 (3): 320- 331
https://doi.org/10.1016/0095-8956(79)90021-2
13 T Bilski . Optimum embedding of complete graphs in books. Discrete Math., 1998, 182 (1/2/3): 21- 28
14 J F Buss , P W Shor . 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 C Chen . Any maximal planar graph with only one separating triangle is hamiltonian. J. Comb. Opim., 2003, 7 (1): 79- 86
https://doi.org/10.1023/A:1021998507140
16 N Chiba , T Nishizeki . The hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs. J. Algorithms, 1989, 10 (2): 187- 211
https://doi.org/10.1016/0196-6774(89)90012-6
17 F R K Chung , F T Leighton , A L Rosenberg . Embedding graphs in books: a layout problem with applications to VLSI design. SIAM J. Algebraic Discrete Methods, 1987, 8 (1): 33- 58
https://doi.org/10.1137/0608002
18 V Dujmović , D R Wood . Graph treewidth and geometric thickness parameters. Discrete Comput. Geom., 2007, 37 (4): 641- 670
https://doi.org/10.1007/s00454-007-1318-7
19 T Endo . The pagenumber of toroidal graphs is at most seven. Discrete Math., 1997, 175 (1/2/3): 87- 96
20 H Enomoto , M S Miyauchi . 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
https://doi.org/10.1137/S0895480195280319
21 H Enomoto , M S Miyauchi , K Ota . 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 H Enomoto , T Nakamigawa , K Ota . On the pagenumber of complete bipartite graphs. J. Combin. Theory Ser. B, 1997, 71 (1): 111- 120
https://doi.org/10.1006/jctb.1997.1773
23 S Even , A Itai . Queues, stacks, and graphs. In: Theory of Machines and Computations (Proc. Internat. Sympos., Technion, Haifa, 1971), New York: Academic Press, 1971, 71- 86
24 G Ewald . Hamiltonian circuits in simplicial complexes. Geometriae Dedicata, 1973, 2: 115- 125
25 J F Fang , K C Lai . Embedding the incomplete hypercube in books. Inform. Process. Lett., 2005, 96 (1): 1- 6
https://doi.org/10.1016/j.ipl.2005.05.026
26 R A Games . Optimal book embeddings of the FFT, benes, and barrel shifter networks. Algorithmica, 1986, 1 (1): 233- 250
27 J L Ganley , L S Heath . The pagenumber of k-trees is O(k). Discrete Appl. Math., 2001, 109 (3): 215- 221
https://doi.org/10.1016/S0166-218X(00)00178-5
28 M R Garey , D S Johnson , G L Miller , C H Papadimitriou . The complexity of coloring circular arcs and chords. SIAM J. Algebraic Discrete Methods, 1980, 1 (2): 216- 227
https://doi.org/10.1137/0601025
29 A Grigoriev , H L Bodlaender . Algorithms for graphs embeddable with few crossings per edge. Algorithmica, 2007, 49 (1): 1- 11
https://doi.org/10.1007/s00453-007-0010-x
30 X X Guan . Book-embedding of Planar Graphs. Master Thesis, Taiyuan: Taiyuan University of Technology, 2019 (in Chinese)
31 X X Guan , W H Yang . Embedding planar 5-graphs in three pages. Discrete Appl. Math., 2019, 282: 108- 121
32 T Hasunuma , Y Shibata . Embedding de Bruijn, Kautz and shuffle-exchange networks in books. Discrete Appl. Math., 1997, 78 (1/2/3): 103- 116
33 L S Heath . Embedding planar graphs in seven pages. In: 25th Annual Symposium on Foundations of Computer Science, New York: IEEE, 1984, 74- 89
34 L S Heath . Algorithms for Embedding Graphs in Books. Ph.D. Thesis, Chapel Hill, NC: University of North Carolina, 1985
35 L S Heath , S Istrail . The pagenumber of genus g graphs is O(g). J. Assoc. Comput. Mach., 1992, 39 (3): 479- 501
https://doi.org/10.1145/146637.146643
36 G Helden . Each maximal planar graph with exactly two separating triangles is hamiltonian. Discret. Appl. Mach., 2007, 155 (14): 1833- 1836
https://doi.org/10.1016/j.dam.2007.03.018
37 M Hoffmann , B Klemz . 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 F K Hwang . A survey on multi-loop networks. Theoret. Comput. Sci., 2003, 299 (1/2/3): 107- 121
39 S Istrail . 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 S S Joslin , P C Kainen , S Overbay . On dispersability of some cycle products. Missouri J. Math. Sci., in press, 2021
41 P C Kainen . Some recent results in topological graph theory. In: Graphs and Combinatorics. Lecture Notes in Math., Vol. 406, Berlin: Springer, 1974, 76- 108
42 P C Kainen . Complexity of products of even cycles. Bull. Inst. Combinatorics and Its Applications, 2011, 62: 95- 102
43 P C Kainen , S Overbay . Extension of a theorem of Whitney. Appl. Math. Lett., 2007, 20: 835- 837
https://doi.org/10.1016/j.aml.2006.08.019
44 P C Kainen , S Overbay . Cubic planar bipartite graphs are dispersable. arXiv: 2107. 4728v1
45 P C Kainen , S Overbay . On matching book thickness. in preparation
46 N Kapoor , M Russell , I Stojmenovic , A Y Zomaya . A genetic algorithm for finding the pagenumber of interconnection networks. J. Parallel Distrib. Comput., 2002, 62 (2): 267- 283
https://doi.org/10.1006/jpdc.2001.1789
47 S G Kobourov , G Liotta , F Montecchiani . An annotated bibliography on 1-planarity. Computer Science Review 25, 2017, 49- 67
48 M Konoe , K Hagiwara , N Tokura . On the pagenumber of hypercubes and cube-connected cycles. IEICE Trans., 1988, J71-D (3): 490- 500 (in Japanese)
49 V P Korzhik , B Mohar . Minimal obstructions for 1-immersions and hardness of 1-planarity testing. J. Graph Theory, 2013, 72 (1): 30- 71
https://doi.org/10.1002/jgt.21630
50 A B Kwiatkowska . 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 X L Li . Book Embedding of Graphs. Ph.D. Thesis, Zhengzhou: Zhengzhou University, 2002, 72 (1): 243- 249
52 S M Malitz . Graphs with E edges have pagenumber O(E). J. Algorithms, 1994, 17 (1): 71- 84
https://doi.org/10.1006/jagm.1994.1027
53 S M Malitz . Genus g graphs have pagenumber O(g). J. Algorithms, 1994, 17: 85- 109
https://doi.org/10.1006/jagm.1994.1028
54 S L Mitchel . Linear algorithms to recognize outerplanar and maximal outerplanar graphs. Inform. Process. Lett., 1979, 9 (5): 224- 232
55 S Moran , Y Wolfstahl . One-page book embedding under vertex-neighborhood constraints. SIAM J. Discrete Math., 1990, 3 (3): 376- 390
https://doi.org/10.1137/0403034
56 D J Muder , M L Weaver , D B West . Pagenumber of complete bipartite graphs. J. Graph Theory, 1988, 12 (4): 469- 489
https://doi.org/10.1002/jgt.3190120403
57 A Nakamoto , T Nozawa . Book embedding of locally planar graphs on orientable surfaces. Discrete Math., 2016, 339 (11): 2672- 2679
https://doi.org/10.1016/j.disc.2016.05.006
58 A Nakamoto , K Ozeki . Book embedding of toroidal bipartite graphs. SIAM J. Discrete Math., 2012, 26 (2): 661- 669
https://doi.org/10.1137/100794651
59 R Nowakowski , A Parker . Ordered sets, pagenumbers and planarity. Order, 1989, 6 (3): 209- 218
https://doi.org/10.1007/BF00563521
60 L T Ollmann . 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 S Overbay . Generalized Book Embeddings. Ph. D. Dissertation, Colorado State University, Fort Collins, CO, 1998
62 J Pach , G Tóth . Graphs drawn with few crossings per edge. Combinatorica, 1997, 17 (3): 427- 439
https://doi.org/10.1007/BF01215922
63 S Pupyrev . Private communication
64 S Pupyrev . Book Embeddings of Graph Products. arXiv: 2007.15102v1
65 G Ringel . Map Color Theorem. Die Grundlehren der mathematischen Wissenschaften, Band 209, New York: Springer-Verlag, 1974
66 A L Rosenberg . The Diogenes approach to testable fault-tolerant arrays of processors. IEEE Trans. Comput., 1983, 32 (10): 902- 910
67 D P Sanders . The Diogenes approach to testable fault-tolerant arrays of processors. J. Graph Theory., 1997, 24 (4): 341- 345
https://doi.org/10.1002/(SICI)1097-0118(199704)24:4<341::AID-JGT6>3.0.CO;2-O
68 F Shahrokhi , W P Shi . On crossing sets, disjoint sets, and pagenumber. J. Algorithm, 2000, 34 (1): 40- 53
https://doi.org/10.1006/jagm.1999.1049
69 Z Shao , Y Liu , Z Li . Matching book embedding of the Cartesian product of a complete graph and a cycle. arXiv: 2002.00309v1
70 Z Shao , Y Liu , Z Li . Matching book thickness of Halin graphs. arXiv: 2008.13331v1
71 H C So . 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 K Sperfeld . On the page number of complete odd-partite graphs. Discrete Math., 2013, 313 (17): 1689- 1696
https://doi.org/10.1016/j.disc.2013.04.028
73 R P Swaminathan , D Giraraj , D K Bhatia . The pagenumber of the class of bandwidth-k graphs is k − 1. Inform. Process. Lett., 1995, 55 (2): 71- 74
https://doi.org/10.1016/0020-0190(95)00079-R
74 M M Sysło . Characterizations of outerplanar graphs. Discrete Math., 1979, 26 (1): 47- 53
https://doi.org/10.1016/0012-365X(79)90060-8
75 Y Tanaka , Y Shibata . On the pagenumber of trivalent Cayley graphs. Discrete Appl. Math., 2006, 154 (8): 1279- 1292
https://doi.org/10.1016/j.dam.2006.01.001
76 R Tarjan . Sorting using networks of queues and stacks. J. Assoc. Comput. Mach., 1972, 19: 341- 346
https://doi.org/10.1145/321694.321704
77 C Thomassen . Rectilinear drawings of graphs. J. Graph Theory, 1988, 12 (3): 335- 341
https://doi.org/10.1002/jgt.3190120306
78 C D Thompson . A Complexity Theory for VLSI. Ph.D. Thesis, Pittsburgh, PA: Carnegie Mellon University, 1980
79 W T Tutte . A theorem on planar graphs. Trans. Amer. Math. Soc., 1956, 82: 99- 116
https://doi.org/10.1090/S0002-9947-1956-0081471-8
80 M Wang . Some results for embedding grid graphs in books. J. Zhengzhou Univ. (Nat. Sci. Ed.), 1997, 29 (2): 31- 34 (in Chinese)
81 H Whitney . A theorem on graphs. Ann. Math. 1931, 32: 378- 390
https://doi.org/10.2307/1968197
82 A Wigderson . The complexity of the Hamiltonian circuit problem for maximal planar graphs. Technical Report 298, Department of EECS, Princeton University, February (1982)
83 D R Wood . Degree constrained book embeddings. J. Algorithms, 2002, 45 (2): 144- 154
https://doi.org/10.1016/S0196-6774(02)00249-3
84 W H Yang , J X Meng . Embedding connected double-loop networks with even cardinality in books. Appl. Math. Lett., 2009, 22 (9): 1458- 1461
https://doi.org/10.1016/j.aml.2009.01.059
85 M Yannakakis . 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 M Yannakakis . Embedding planar graphs in four pages. J. Comput. System Sci., 1989, 38 (1): 36- 67
https://doi.org/10.1016/0022-0000(89)90032-9
87 M Yannakakis . Planar Graphs that Need Four Pages. J. Combin. Theory Ser. B, 2020, 145: 241- 263
https://doi.org/10.1016/j.jctb.2020.05.008
88 Y M Zhang , G L Chen . The results of embedding several graphs in books. Chinese J. Computer, 1993, 16 (7): 509- 518 (in Chinese)
89 B Zhao . The Book Embedding of Some Graphs. Ph.D. Thesis, Urumqi: Xinjiang University, 2016 (in Chinese)
90 B Zhao , L H Chen , Y P Zhang , Y Z Tian , J X Meng . On the page number of triple-loop networks with even cardinality. Ars Combin., 2016, 124: 257- 266
91 B Zhao , J X Meng . Embedding connected double-loop networks with odd cardinality in books. J. Xinjiang Univ. (Nat. Sci. Ed.), 2011, 28 (2): 152- 155
92 B Zhao , Y Z Tian , J X Meng . Embedding semistrong product of paths and cycles in books. J. Nat. Sci. Hunan Norm. Univ., 2015, 38 (6): 73- 77
93 B Zhao , Y Z Tian , J X Meng . 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 B Zhao , W Xiong , Y Z Tian , J X Meng . Embedding generalized Petersen graph in books. Chin. Ann. Math. Ser. B, 2016, 37 (3): 385- 394
https://doi.org/10.1007/s11401-016-1010-4
[1] Bobo HUA,Yong LIN. Curvature notions on graphs[J]. Front. Math. China, 2016, 11(5): 1275-1290.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed