Please wait a minute...
北京大学期刊网 | 作者  审稿人  编委专家  工作人员

首页   |   关于   |   浏览   |   投稿指南   |   新闻公告
数学进展 - 2020, Vol. 49(1): 1-12
综述文章
平面图书式嵌入综述
A Survey on Book-embedding of Planar Graphs

关夏夏1, 吴楚雄1, 杨卫华1, 孟吉翔2,*
GUAN Xiaxia1, WU Chuxiong1, YANG Weihua1, MENG Jixiang2

1. 太原理工大学数学学院, 太原, 山西, 030024;
2. 新疆大学数学与系统科学学院, 乌鲁木齐, 新疆, 830046
1. College of Mathematics, Taiyuan University of Technology, Taiyuan, Shanxi, 030024, P. R. China;
2. College of Mathematics and System Science, Xinjiang University, Urumqi, Xinjiang, 830046, P. R. China

收稿日期: 2019-05-30
出版日期: 2020-03-25
2020, Vol. 49(1): 1-12
DOI: 10.11845/sxjz.2019007a


PDF
[464 KB]
194
下载
461
浏览

引用导出
0
    /   /   推荐

摘要 图书式嵌入问题主要起源于大型集成电路(VLSI)设计和多层线路板印刷(PCBs)设计等诸多领域, 有广泛的应用价值. 图的书式嵌入是将图的点集排在一条直线上(书脊)且将边嵌入到以书脊为边界的半平面上(页)使得同页中的边互不相交. 其研究的一个重要参数是页数(满足条件所需的最小页数), 该问题是NP-困难的. 本文主要综述平面图书式嵌入问题的相关研究.
关键词 书式嵌入平面图页数    
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 wordsbook embedding    planar graphs    pagenumber
PACS:  O157.5  
基金资助:国家自然科学基金(No. 11671296).
通讯作者: E-mail: * mjx@xju.edu.cn   
[1] Alam M.J., Brandenburg F.J. and Kobourov S.G., On the book thickness of 1-planar graphs,2015, arXiv: 1510.05891 [cs.CG].
[2] Alam M.J., Brandenburg F.J. and 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] Alhashem M., Jourdan G.V. and Zaguia N., On the book embedding of ordered sets, Ars Combin., 2015, 119: 47-64.
[4] Angelini P.,Da Lozzo, G. and Neuwirth, D., Advancements on SEFE and partitioned book embedding problems, Theoret. Comput. Sci., 2015, 575: 71-89.
[5] 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.
[6] Balogh, J. and Salazar, G., Book embeddings of regular graphs, SIAM J. Discrete Math., 2015, 29(2): 811-822.
[7] Bekos M.A., Bruckdorfer T., Kaufmann M. and 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.
[8] Bekos M.A., Gronemann M. and Raftopoulou C.N., Two-page book embeddings of 4-planar graphs, Algorithmica, 2016, 75(1): 158-185.
[9] Bekos M.A., Kaufmann M. and 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.
[10] Bernhart, F. and Kainen, P.C., The book thickness of a graph, J. Combin. Theory Ser. B, 1979, 27(3): 320-331.
[11] Bilski T.,Optimum embedding of complete graphs in books, Discrete Math., 1998, 182(1/2/3): 21-28.
[12] Buss, J.F. and 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.
[13] Chung F.R.K., Leighton, F.T. and 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.
[14] Dujmović, V. and Wood, D.R., Graph treewidth and geometric thickness parameters, Discrete Comput. Geom., 2007, 37(4): 641-670.
[15] Endo T.,The pagenumber of toroidal graphs is at most seven, Discrete Math., 1997, 175(1/2/3): 87-96.
[16] Enomoto, H. and 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.
[17] Enomoto H., Miyauchi M.S. and 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.
[18] Enomoto H., Nakamigawa T. and Ota K., On the pagenumber of complete bipartite graphs, J. Combin. Theory Ser. B, 1997, 71(1): 111-120.
[19] Even, S. and 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.
[20] Ewald G.,Hamiltonian circuits in simplicial complexes, Geometriae Dedicata, 1973, 2: 115-125.
[21] Fang, J.-F. and Lai, K.-C., Embedding the incomplete hypercube in books, Inform. Process. Lett., 2005, 96(1): 1-6.
[22] Games R.A.,Optimal book embeddings of the FFT, benes, and barrel shifter networks, Algorithmica, 1986, 1(1): 233-250.
[23] Ganley, J.L. and Heath, L.S., The pagenumber of $k$-trees is $O(k)$, Discrete Appl. Math., 2001, 109(3): 215-221.
[24] Garey M.R., Johnson D.S., Miller G.L. and Papadimitriou C.H., The complexity of coloring circular arcs and chords, SIAM [J]. Algebraic Discrete Methods, 1980, 1(2): 216-227.
[25] Guan X.X.,Book-embedding of Planar Graphs, Master Thesis, Taiyuan: Taiyuan University of Technology, 2019 (in Chinese).
[26] Guan, X.X. and Yang, W.H.,Embedding planar 5-graphs in three pages, Discrete Appl. Math., 2019, in press, https://doi.org/10.1016/j.dam.2019.11.020.
[27] Hasunuma, T. and Shibata, Y., Embedding de Bruijn, Kautz and shuffle-exchange networks in books, Discrete Appl. Math., 1997, 78(1/2/3): 103-116.
[28] Heath L.S.,Embedding planar graphs in seven pages, In: 25th Annual Symposium on Foundations of Computer Science, New York: IEEE, 1984, 74-89.
[29] Heath L.S.,Algorithms for Embedding Graphs in Books, Ph.D. Thesis, Chapel Hill, NC: University of North Carolina, 1985.
[30] Heath, L.S. and Istrail, S., The pagenumber of genus $g$ graphs is $O(g)$, J. Assoc. Comput. Mach., 1992, 39(3): 479-501.
[31] Hoffmann, M. and 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.
[32] Hwang F.K.,A survey on multi-loop networks, Theoret. Comput. Sci., 2003, 299(1/2/3): 107-121.
[33] 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.
[34] 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.
[35] Kapoor N., Russell M., Stojmenovic I. and Zomaya A.Y., A genetic algorithm for finding the pagenumber of interconnection networks, J. Parallel Distrib. Comput., 2002, 62(2): 267-283.
[36] Konoe M., Hagiwara K. and Tokura N., On the pagenumber of hypercubes and cube-connected cycles, IEICE Trans.,1988, J71-D(3): 490-500 (in Japanese).
[37] Korzhik, V.P. and Mohar, B., Minimal obstructions for 1-immersions and hardness of 1-planarity testing, [J]. Graph Theory, 2013, 72(1): 30-71.
[38] 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.
[39] Li X.L.,Book Embedding of Graphs, Ph.D. Thesis, Zhengzhou: Zhengzhou University, 2002 (in Chinese).
[40] Malitz S.M.,Graphs with $E$ edges have pagenumber $O(\sqrt{E})$, [J]. Algorithms, 1994, 17(1): 71-84.
[41] Malitz S.M.,Genus $g$ graphs have pagenumber $O(\sqrt{g})$, [J]. Algorithms, 1994, 17: 85-109.
[42] Mitchel S.L.,Linear algorithms to recognize outerplanar and maximal outerplanar graphs, Inform. Process. Lett., 1979, 9(5): 224-232.
[43] Moran, S. and Wolfstahl, Y., One-page book embedding under vertex-neighborhood constraints, SIAM J. Discrete Math., 1990, 3(3): 376-390.
[44] Muder D.J., Weaver M.L. and West D.B., Pagenumber of complete bipartite graphs, [J]. Graph Theory, 1988, 12(4): 469-489.
[45] Nakamoto, A. and Nozawa, T., Book embedding of locally planar graphs on orientable surfaces, Discrete Math., 2016, 339(11): 2672-2679.
[46] Nakamoto, A. and Ozeki, K., Book embedding of toroidal bipartite graphs, SIAM J. Discrete Math., 2012, 26(2): 661-669.
[47] Nowakowski, R. and Parker, A., Ordered sets, pagenumbers and planarity, Order, 1989, 6(3): 209-218.
[48] 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.
[49] Pach, J. and Tóth, G., Graphs drawn with few crossings per edge, Combinatorica, 1997, 17(3): 427-439.
[50] Pupyrev S.,Private communication, http://be.cs.arizona.edu/static/img/deg7_non_hamiltonian.png.
[51] Ringel G.,Map Color Theorem, Die Grundlehren der mathematischen Wissenschaften, Band 209, New York: Springer-Verlag, 1974.
[52] Rosenberg A.L.,The Diogenes approach to testable fault-tolerant arrays of processors, IEEE Trans. Comput., 1983, 32(10): 902-910.
[53] Shahrokhi, F. and Shi, W.P., On crossing sets, disjoint sets, and pagenumber, [J]. Algorithm, 2000, 34(1): 40-53.
[54] 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.
[55] Sperfeld K.,On the page number of complete odd-partite graphs, Discrete Math., 2013, 313(17): 1689-1696.
[56] Swaminathan R.P., Giraraj D. and Bhatia D.K., The pagenumber of the class of bandwidth-$k$ graphs is $k-1$, Inform. Process. Lett., 1995, 55(2): 71-74.
[57] Sysło M.M.,Characterizations of outerplanar graphs, Discrete Math., 1979, 26(1): 47-53.
[58] Tanaka, Y. and Shibata, Y., On the pagenumber of trivalent Cayley graphs, Discrete Appl. Math., 2006, 154(8): 1279-1292.
[59] Tarjan R.,Sorting using networks of queues and stacks, J. Assoc. Comput. Mach., 1972, 19: 341-346.
[60] Thomassen C.,Rectilinear drawings of graphs, [J]. Graph Theory, 1988, 12(3): 335-341.
[61] Thompson C.D.,A Complexity Theory for VLSI, Ph.D. Thesis, Pittsburgh, PA: Carnegie Mellon University, 1980.
[62] Tutte W.T.,A theorem on planar graphs, Trans. Amer. Math. Soc., 1956, 82: 99-116.
[63] Wang M.,Some results for embedding grid graphs in books, J. Zhengzhou Univ. ( Nat. Sci. Ed.), 1997, 29(2): 31-34 (in Chinese).
[64] Wood D.R.,Degree constrained book embeddings, [J]. Algorithms, 2002, 45(2): 144-154.
[65] Yang, W.H. and Meng, J.X., Embedding connected double-loop networks with even cardinality in books, Appl. Math. Lett., 2009, 22(9): 1458-1461.
[66] 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.
[67] Yannakakis M.,Embedding planar graphs in four pages, J. Comput. System Sci., 1989, 38(1): 36-67.
[68] Zhang, Y.M. and Chen, G.L., The results of embedding several graphs in books, Chinese [J]. Computer, 1993, 16(7): 509-518 (in Chinese).
[69] Zhao B.,The Book Embedding of Some Graphs, Ph.D. Thesis, Urumqi: Xinjiang University, 2016 (in Chinese).
[70] Zhao B., Chen L.H., Zhang Y.P., Tian Y.Z. and Meng J.X., On the page number of triple-loop networks with even cardinality, Ars Combin., 2016, 124: 257-266.
[71] Zhao, B. and Meng, J.X., Embedding connected double-loop networks with odd cardinality in books, J. Xinjiang Univ. ( Nat. Sci. Ed.), 2011, 28(2): 152-155.
[72] Zhao B., Tian Y.Z. and Meng J.X., Embedding semistrong product of paths and cycles in books, J. Nat. Sci. Hunan Norm. Univ., 2015, 38(6): 73-77.
[73] Zhao B., Tian Y.Z. and 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.
[74] Zhao B., Xiong W., Tian Y.Z. and Meng J.X., Embedding generalized Petersen graph in books, Chin. Ann. Math. Ser. B, 2016, 37(3): 385-394.
[1] 陈敏, 余梦蕾, 李柏翰, 范佳清. 外平面图的弱边面染色[J]. 数学进展, 2020, 49(2): 165-171.
[2] 卜月华,王丽霞. 稀疏平面图的2-距离染色[J]. 数学进展, 2019, 48(2): 145-155.
[3] 王茂群, 杨卫华. 原图是平面图的4-连通线图的哈密尔顿连通性[J]. 数学进展, 2019, 48(1): 29-34.
[4] 卜月华, 叶飘飘. 围长至少为 $\mathbf{5}$ 的平面图的 $\mathrm{\mathbf{injective}}$-染色[J]. 数学进展, 2018, 47(3): 363-372.
[5] 邓兴超, 宋贺, 苏贵福, 田润丽. 小直径二连通外平面图的彩虹连通数[J]. 数学进展, 2018, 47(3): 373-382.
[6] 卜月华, 商春慧. 不含4-圈平面图的2-距离染色[J]. 数学进展, 2017, 46(3): 342-354.
[7] 李晓艳,陈敏,王应前. 关于无5-, 6-及7-圈的平面图的3-可选性[J]. 数学进展, 2016, 45(4): 491-499.
[8] 景昱波,王应前. 可平面图的线性2-荫度的新上限[J]. 数学进展, 2016, 45(2): 185-189.
[9] 卜月华,严晓燕. 不含3, 4, 8-圈的平面图的2-距离染色[J]. 数学进展, 2015, 44(2): 208-218.
[10] 卜月华,严晓燕. 不含3, 4, 8-圈的平面图的2-距离染色[J]. 数学进展, 2014, 43(7): 13055-.
[11] 魏二玲;刘彦佩;. (邻接)树图的同构及平面性[J]. 数学进展, 2009, 38(2): 220-226.
[12] 李珍萍;章祥荪;. 平面图的循环色数与临界性(英文)[J]. 数学进展, 2006, 35(5): 595-606.
[13] 王宜举. 图的星临界性(英文)[J]. 数学进展, 2002, 31(4): 331-336.
Viewed
Full text


Abstract

Cited

  Discussed   
首页 · 关于 · 关于OA · 法律公告 · 收录须知 · 联系我们 · 注册 · 登录


© 2015-2017 北京大学图书馆 .