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.

Key words： 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