A survey on book-embedding of planar graphs. (English) Zbl 1489.05029
Front. Math. China 17, No. 2, 255-273 (2022); translation from Adv. Math., Beijing 49, No. 1, 1–12 (2020).
Summary: 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.
MSC:
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 05C60 | Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) |
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, Graph Drawing, 83-94 (2013), Cham: Springer, Cham · Zbl 1406.68054 · doi:10.1007/978-3-319-03841-4_8 |
| [3] | Alam M J, Bekos M A, Gronemann M, Kaufmann M, Pupyrev S. On dispersable book embeddings. Graph-theoretic Concepts in Computer Science (44th International Workshop, WG 2018, Cottbus, Germany), A. Brandestadt, E. Kohler, K. Meer, Eds., LNCS 11159 (2018) 1-14, Springer, Cham, Switzerland · Zbl 1497.68363 |
| [4] | Alam, M. J.; Bekos, M. A.; Gronemann, M.; Kaufmann, M.; Pupyrev, S., On dispersable book embeddings, Theoret. Comput. Sci., 861, 1-22 (2021) · Zbl 1497.68362 · doi:10.1016/j.tcs.2021.01.035 |
| [5] | Alhashem, M.; Jourdan, G. V.; Zaguia, N., On the book embedding of ordered sets, Ars Combin., 119, 47-64 (2015) · Zbl 1349.05240 |
| [6] | Angelini, P.; Da Lozzo, G.; Neuwirth, D., Advancements on SEFE and partitioned book embedding problems, Theoret. Comput. Sci., 575, 71-89 (2015) · Zbl 1309.68078 · doi:10.1016/j.tcs.2014.11.016 |
| [7] | Atneosen, G. A., On the Embeddability of Compacta in N-books: Intrinsic and Extrinsic Properties (1968), East Lansing, MI: Michigan State University, East Lansing, MI |
| [8] | Balogh, J.; Salazar, G., Book embeddings of regular graphs, SIAM J. Discrete Math., 29, 2, 811-822 (2015) · Zbl 1329.05212 · doi:10.1137/140961183 |
| [9] | Bekos, M. A.; Bruckdorfer, T.; Kaufmann, M.; Raftopoulou, C., 1-planar graphs have constant book thickness, Algorithms—ESA 2015, 130-141 (2015), Heidelberg: Springer, Heidelberg · Zbl 1370.05046 · doi:10.1007/978-3-662-48350-3_12 |
| [10] | Bekos, M. A.; Gronemann, M.; Raftopoulou, C. N., Two-page book embeddings of 4-planar graphs, Algorithmica, 75, 1, 158-185 (2016) · Zbl 1339.05066 · doi:10.1007/s00453-015-0016-8 |
| [11] | Bekos, M. A.; Kaufmann, M.; Zielke, C., The book embedding problem from a SAT-solving perspective, Graph Drawing and Network Visualization, 125-138 (2015), Cham: Springer, Cham · Zbl 1471.68184 · doi:10.1007/978-3-319-27261-0_11 |
| [12] | Bernhart, F.; Kainen, P. C., The book thickness of a graph, J. Combin. Theory Ser. B, 27, 3, 320-331 (1979) · Zbl 0427.05028 · doi:10.1016/0095-8956(79)90021-2 |
| [13] | Bilski, T., Optimum embedding of complete graphs in books, Discrete Math., 182, 1-2, 21-28 (1998) · Zbl 0911.05055 · doi:10.1016/S0012-365X(97)00131-3 |
| [14] | Buss, J. F.; Shor, P. W., On the pagenumber of planar graphs, 98-100 (1984), New York, NY: ACM, New York, NY |
| [15] | Chen, C., Any maximal planar graph with only one separating triangle is hamiltonian, J. Comb. Opim., 7, 1, 79-86 (2003) · Zbl 1046.90072 · doi:10.1023/A:1021998507140 |
| [16] | Chiba, N.; Nishizeki, T., The hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs, J. Algorithms, 10, 2, 187-211 (1989) · Zbl 0689.68089 · doi:10.1016/0196-6774(89)90012-6 |
| [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, 8, 1, 33-58 (1987) · Zbl 0617.68062 · doi:10.1137/0608002 |
| [18] | Dujmović, V.; Wood, D. R., Graph treewidth and geometric thickness parameters, Discrete Comput. Geom., 37, 4, 641-670 (2007) · Zbl 1118.05018 · doi:10.1007/s00454-007-1318-7 |
| [19] | Endo, T., The pagenumber of toroidal graphs is at most seven, Discrete Math., 175, 1-2, 87-96 (1997) · Zbl 0888.05019 · doi:10.1016/S0012-365X(96)00144-6 |
| [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., 12, 3, 337-341 (1999) · Zbl 0933.05043 · doi:10.1137/S0895480195280319 |
| [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., 92, 2-3, 149-155 (1999) · Zbl 0933.05042 · doi:10.1016/S0166-218X(99)00044-X |
| [22] | Enomoto, H.; Nakamigawa, T.; Ota, K., On the pagenumber of complete bipartite graphs, J. Combin. Theory Ser. B, 71, 1, 111-120 (1997) · Zbl 0902.05019 · doi:10.1006/jctb.1997.1773 |
| [23] | Even, S.; Itai, A., Queues, stacks, and graphs, Theory of Machines and Computations (Proc. Internat. Sympos., Technion, Haifa, 1971), 71-86 (1971), New York: Academic Press, New York · doi:10.1016/B978-0-12-417750-5.50011-7 |
| [24] | Ewald, G., Hamiltonian circuits in simplicial complexes, Geometriae Dedicata, 2, 115-125 (1973) · Zbl 0272.57008 · doi:10.1007/BF00149287 |
| [25] | Fang, J. F.; Lai, K. C., Embedding the incomplete hypercube in books, Inform. Process. Lett., 96, 1, 1-6 (2005) · Zbl 1184.68100 · doi:10.1016/j.ipl.2005.05.026 |
| [26] | Games, R. A., Optimal book embeddings of the FFT, benes, and barrel shifter networks, Algorithmica, 1, 1, 233-250 (1986) · Zbl 0639.94022 · doi:10.1007/BF01840445 |
| [27] | Ganley, J. L.; Heath, L. S., The pagenumber of k-trees is O(k), Discrete Appl. Math., 109, 3, 215-221 (2001) · Zbl 0976.68116 · doi:10.1016/S0166-218X(00)00178-5 |
| [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, 1, 2, 216-227 (1980) · Zbl 0499.05058 · doi:10.1137/0601025 |
| [29] | Grigoriev, A.; Bodlaender, H. L., Algorithms for graphs embeddable with few crossings per edge, Algorithmica, 49, 1, 1-11 (2007) · Zbl 1131.68120 · doi:10.1007/s00453-007-0010-x |
| [30] | Guan, X. X., Book-embedding of Planar Graphs (2019), Taiyuan: Taiyuan University of Technology, Taiyuan |
| [31] | Guan, X. X.; Yang, W. H., Embedding planar 5-graphs in three pages, Discrete Appl. Math., 282, 108-121 (2019) · Zbl 1441.05160 · doi:10.1016/j.dam.2019.11.020 |
| [32] | Hasunuma, T.; Shibata, Y., Embedding de Bruijn, Kautz and shuffle-exchange networks in books, Discrete Appl. Math., 78, 1-2, 103-116 (1997) · Zbl 0890.68100 · doi:10.1016/S0166-218X(97)00009-7 |
| [33] | Heath, L. S., Embedding planar graphs in seven pages, 74-89 (1984), New York: IEEE, New York |
| [34] | Heath, L. S., Algorithms for Embedding Graphs in Books (1985), Chapel Hill, NC: University of North Carolina, Chapel Hill, NC |
| [35] | Heath, L. S.; Istrail, S., The pagenumber of genus g graphs is O(g), J. Assoc. Comput. Mach., 39, 3, 479-501 (1992) · Zbl 0799.68152 · doi:10.1145/146637.146643 |
| [36] | Helden, G., Each maximal planar graph with exactly two separating triangles is hamiltonian, Discret. Appl. Mach., 155, 14, 1833-1836 (2007) · Zbl 1123.05059 · doi:10.1016/j.dam.2007.03.018 |
| [37] | Hoffmann, M.; Klemz, B.; Bender, MA; Svensson, O.; Herman, G., Triconnected planar graphs of maximum degree five are subhamiltonian, 27th Annual European Symposium on Algorithms (ESA 2019), 14 pp (2019), Dagstuhl: Schloss Dagstuhl—Leibniz-Zentrum für Informatik, Dagstuhl |
| [38] | Hwang, F. K., A survey on multi-loop networks, Theoret. Comput. Sci., 299, 1-2, 107-121 (2003) · Zbl 1038.68004 · doi:10.1016/S0304-3975(01)00341-3 |
| [39] | Istrail, S., An algorithm for embedding planar graphs in six pages, An. Ştiinţ. Univ. Al. I. Cuza Iaşi Secţ. I a Mat., 34, 4, 329-341 (1988) · Zbl 0688.68069 |
| [40] | Joslin S S, Kainen P C, Overbay S. On dispersability of some cycle products. Missouri J. Math. Sci., in press, 2021 · Zbl 1485.05061 |
| [41] | Kainen, P. C., Some recent results in topological graph theory, Graphs and Combinatorics, 76-108 (1974), Berlin: Springer, Berlin · Zbl 0319.05103 · doi:10.1007/BFb0066436 |
| [42] | Kainen, P. C., Complexity of products of even cycles, Bull. Inst. Combinatorics and Its Applications, 62, 95-102 (2011) · Zbl 1257.05102 |
| [43] | Kainen, P. C.; Overbay, S., Extension of a theorem of Whitney, Appl. Math. Lett., 20, 835-837 (2007) · Zbl 1131.05035 · doi:10.1016/j.aml.2006.08.019 |
| [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., 62, 2, 267-283 (2002) · Zbl 1006.68112 · doi:10.1006/jpdc.2001.1789 |
| [47] | Kobourov, S. G.; Liotta, G.; Montecchiani, F., An annotated bibliography on 1-planarity, Computer Science Review, 25, 49-67 (2017) · Zbl 1398.68402 · doi:10.1016/j.cosrev.2017.06.002 |
| [48] | Konoe, M.; Hagiwara, K.; Tokura, N., On the pagenumber of hypercubes and cube-connected cycles, IEICE Trans., J71-D, 3, 490-500 (1988) |
| [49] | Korzhik, V. P.; Mohar, B., Minimal obstructions for 1-immersions and hardness of 1-planarity testing, J. Graph Theory, 72, 1, 30-71 (2013) · Zbl 1259.05046 · doi:10.1002/jgt.21630 |
| [50] | Kwiatkowska, A. B., On page number of N-free posets, Fifth Cracow Conference on Graph Theory USTRON’ 06, Electron, 243-249 (2006), Amsterdam: Elsevier Sci. B. V., Amsterdam · Zbl 1202.06003 |
| [51] | Li, X. L., Book Embedding of Graphs (2002), Zhengzhou: Zhengzhou University, Zhengzhou |
| [52] | Malitz, S. M., Graphs with E edges have pagenumber \(O(\sqrt E )\), J. Algorithms, 17, 1, 71-84 (1994) · Zbl 0810.68102 · doi:10.1006/jagm.1994.1027 |
| [53] | Malitz, S. M., Genus g graphs have pagenumber \(O(\sqrt g )\), J. Algorithms, 17, 85-109 (1994) · Zbl 0810.68103 · doi:10.1006/jagm.1994.1028 |
| [54] | Mitchel, S. L., Linear algorithms to recognize outerplanar and maximal outerplanar graphs, Inform. Process. Lett., 9, 5, 224-232 (1979) · Zbl 0444.68055 · doi:10.1016/0020-0190(79)90075-9 |
| [55] | Moran, S.; Wolfstahl, Y., One-page book embedding under vertex-neighborhood constraints, SIAM J. Discrete Math., 3, 3, 376-390 (1990) · Zbl 0742.05060 · doi:10.1137/0403034 |
| [56] | Muder, D. J.; Weaver, M. L.; West, D. B., Pagenumber of complete bipartite graphs, J. Graph Theory, 12, 4, 469-489 (1988) · Zbl 0662.05020 · doi:10.1002/jgt.3190120403 |
| [57] | Nakamoto, A.; Nozawa, T., Book embedding of locally planar graphs on orientable surfaces, Discrete Math., 339, 11, 2672-2679 (2016) · Zbl 1339.05080 · doi:10.1016/j.disc.2016.05.006 |
| [58] | Nakamoto, A.; Ozeki, K., Book embedding of toroidal bipartite graphs, SIAM J. Discrete Math., 26, 2, 661-669 (2012) · Zbl 1248.05048 · doi:10.1137/100794651 |
| [59] | Nowakowski, R.; Parker, A., Ordered sets, pagenumbers and planarity, Order, 6, 3, 209-218 (1989) · Zbl 0701.06005 · doi:10.1007/BF00563521 |
| [60] | Ollmann, L. T., On the book thicknesses of various graphs, Proceedings of the 4th Southeastern Conference on Combinatorics, 459 (1973), Winnipeg, Man.: Utilitas Mathematica Publishing Inc., Winnipeg, Man. |
| [61] | Overbay, S., Generalized Book Embeddings (1998), Fort Collins, CO: Colorado State University, Fort Collins, CO |
| [62] | Pach, J.; Tóth, G., Graphs drawn with few crossings per edge, Combinatorica, 17, 3, 427-439 (1997) · Zbl 0902.05017 · doi:10.1007/BF01215922 |
| [63] | Pupyrev S. Private communication. http://be.cs.arizona.edu/static/img/deg7_non_hamiltonian.png |
| [64] | Pupyrev S. Book Embeddings of Graph Products. arXiv: 2007.15102v1 |
| [65] | Ringel, G., Map Color Theorem (1974), New York: Springer-Verlag, New York · Zbl 0287.05102 · doi:10.1007/978-3-642-65759-7 |
| [66] | Rosenberg, A. L., The Diogenes approach to testable fault-tolerant arrays of processors, IEEE Trans. Comput., 32, 10, 902-910 (1983) · doi:10.1109/TC.1983.1676134 |
| [67] | Sanders, D. P., The Diogenes approach to testable fault-tolerant arrays of processors, J. Graph Theory., 24, 4, 341-345 (1997) · Zbl 0880.05059 · doi:10.1002/(SICI)1097-0118(199704)24:4<341::AID-JGT6>3.0.CO;2-O |
| [68] | Shahrokhi, F.; Shi, W. P., On crossing sets, disjoint sets, and pagenumber, J. Algorithm, 34, 1, 40-53 (2000) · Zbl 0958.68130 · doi:10.1006/jagm.1999.1049 |
| [69] | Shao Z, Liu Y, Li Z. Matching book embedding of the Cartesian product of a complete graph and a cycle. arXiv: 2002.00309v1 · Zbl 1513.05271 |
| [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, 296-303 (1974), New York: IEEE, New York |
| [72] | Sperfeld, K., On the page number of complete odd-partite graphs, Discrete Math., 313, 17, 1689-1696 (2013) · Zbl 1277.05073 · doi:10.1016/j.disc.2013.04.028 |
| [73] | Swaminathan, R. P.; Giraraj, D.; Bhatia, D. K., The pagenumber of the class of bandwidth-k graphs is k − 1, Inform. Process. Lett., 55, 2, 71-74 (1995) · Zbl 0875.68691 · doi:10.1016/0020-0190(95)00079-R |
| [74] | Sysło, M. M., Characterizations of outerplanar graphs, Discrete Math., 26, 1, 47-53 (1979) · Zbl 0401.05040 · doi:10.1016/0012-365X(79)90060-8 |
| [75] | Tanaka, Y.; Shibata, Y., On the pagenumber of trivalent Cayley graphs, Discrete Appl. Math., 154, 8, 1279-1292 (2006) · Zbl 1092.05029 · doi:10.1016/j.dam.2006.01.001 |
| [76] | Tarjan, R., Sorting using networks of queues and stacks, J. Assoc. Comput. Mach., 19, 341-346 (1972) · Zbl 0243.68004 · doi:10.1145/321694.321704 |
| [77] | Thomassen, C., Rectilinear drawings of graphs, J. Graph Theory, 12, 3, 335-341 (1988) · Zbl 0649.05051 · doi:10.1002/jgt.3190120306 |
| [78] | Thompson, C. D., A Complexity Theory for VLSI (1980), Pittsburgh, PA: Carnegie Mellon University, Pittsburgh, PA |
| [79] | Tutte, W. T., A theorem on planar graphs, Trans. Amer. Math. Soc., 82, 99-116 (1956) · Zbl 0070.18403 · doi:10.1090/S0002-9947-1956-0081471-8 |
| [80] | Wang, M., Some results for embedding grid graphs in books, J. Zhengzhou Univ. (Nat. Sci. Ed.), 29, 2, 31-34 (1997) · Zbl 0883.05042 |
| [81] | Whitney, H., A theorem on graphs, Ann. Math., 32, 378-390 (1931) · Zbl 0002.16101 · doi:10.2307/1968197 |
| [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, 45, 2, 144-154 (2002) · Zbl 1052.68105 · doi:10.1016/S0196-6774(02)00249-3 |
| [84] | Yang, W. H.; Meng, J. X., Embedding connected double-loop networks with even cardinality in books, Appl. Math. Lett., 22, 9, 1458-1461 (2009) · Zbl 1173.05327 · doi:10.1016/j.aml.2009.01.059 |
| [85] | Yannakakis, M., Four pages are necessary and sufficient for planar graphs, 104-108 (1986), New York, NY: ACM, New York, NY |
| [86] | Yannakakis, M., Embedding planar graphs in four pages, J. Comput. System Sci., 38, 1, 36-67 (1989) · Zbl 0673.05022 · doi:10.1016/0022-0000(89)90032-9 |
| [87] | Yannakakis, M., Planar Graphs that Need Four Pages, J. Combin. Theory Ser. B, 145, 241-263 (2020) · Zbl 1448.05055 · doi:10.1016/j.jctb.2020.05.008 |
| [88] | Zhang, Y. M.; Chen, G. L., The results of embedding several graphs in books, Chinese J. Computer, 16, 7, 509-518 (1993) |
| [89] | Zhao, B., The Book Embedding of Some Graphs (2016), Urumqi: Xinjiang University, Urumqi |
| [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., 124, 257-266 (2016) · Zbl 1413.05266 |
| [91] | Zhao, B.; Meng, J. X., Embedding connected double-loop networks with odd cardinality in books, J. Xinjiang Univ. (Nat. Sci. Ed.), 28, 2, 152-155 (2011) · Zbl 1265.05170 |
| [92] | Zhao, B.; Tian, Y. Z.; Meng, J. X., Embedding semistrong product of paths and cycles in books, J. Nat. Sci. Hunan Norm. Univ., 38, 6, 73-77 (2015) · Zbl 1349.05191 · doi:10.1007/s11859-015-1061-5 |
| [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.), 33, 1, 1-5 (2016) · Zbl 1363.05221 |
| [94] | Zhao, B.; Xiong, W.; Tian, Y. Z.; Meng, J. X., Embedding generalized Petersen graph in books, Chin. Ann. Math. Ser. B, 37, 3, 385-394 (2016) · Zbl 1338.05059 · doi:10.1007/s11401-016-1010-4 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
