Book embedding of 3-crossing-critical graphs with rational average degree between 3.5 and 4

3rd Indonesian Operations Research Association - International Conference on Operations Research 2018

计算机科学

Pinontoan, B.^1 ; Titaley, J.^1 ; Montolalu, C.E.J.C.^1

Mathematics Department, Sam Ratulangi University, Manado, Indonesia^1

关键词: Average degree;    Book embedding;    Half-planes;   

Others  :  https://iopscience.iop.org/article/10.1088/1757-899X/567/1/012016/pdf
DOI  :  10.1088/1757-899X/567/1/012016

学科分类：计算机科学（综合）

来源: IOP

【 摘 要 】

We consider the graphs P(m, n) with average degree between 3.5 and 4, made up of m identical pieces together with n identical pieces glued together in a circular fashion, such that in any drawing of P(m, n) on the plane, there are exactly three pairwise edges crossings, and when deleting any edge of the graph, the number of crossings of the remaining graph decreases. We then embed P(m, n) into a book such that the vertices are put on a line called the spine and the edges are put on half-planes called the pages, which have the spine as their common boundary, without crossings. In this paper, we show that the minimal number of pages needed to embed P(m, n) into a book is three.