|
|
| |
| On the Pagenumber of 1-Planar Graphs |
| |
Citation： |
Xiaxia GUAN,Weihua YANG.On the Pagenumber of 1-Planar Graphs[J].Chinese Annals of Mathematics B,2025,46(2):287~302 |
| Page view： 466
Net amount： 191 |
Authors： |
Xiaxia GUAN; Weihua YANG |
Foundation： |
the National Natural Science Foundation of China (Nos. 12371356,
12401462) and the Natural Science Foundation of Shanxi Province (No. 20210302123097). |
|
|
| Abstract： |
A book embedding of a graph G is a placement of its vertices along the spine
of a book, and an assignment of its edges to the pages such that no two edges on the same
page cross. The pagenumber of a graph is the minimum number of pages in which it can
be embedded. Determining the pagenumber of a graph is NP-hard. A graph is said to be
1-planar if it can be drawn in the plane so that each edge is crossed at most once. The
anthors prove that the pagenumber of 1-planar graphs is at most 10. |
Keywords： |
Book embedding 1-Planar graph Pagenumber Crossing |
Classification： |
05C10, 68R10 |
|
|
Download PDF Full-Text
|
