Trade off between Page Number and Number of Edge-Crossings on the Spine of Book Embeddings of Graphs

Miki Shimabara MIYAUCHI

Trade off between Page Number and Number of Edge-Crossings on the Spine of Book Embeddings of Graphs

Miki Shimabara MIYAUCHI

Full Text Views

0

Cite this

Summary :

This paper studies the problem of book-embeddings of graphs. When each edge is allowed to appear in one or more pages by crossing the spine of a book, it is well known that every graph G can be embedded in a 3-page book. Recently, it has been shown that there exists a 3-page book embedding of G in which each edge crosses the spine O(log₂ n) times. This paper considers a book with more than three pages. In this case, it is known that a complete graph K_n with n vertices can be embedded in a n/2 -page book without any edge-crossings on the spine. Thus it becomes an interesting problem to devise book-embeddings of G so as to reduce both the number of pages used and the number of edge-crossings over the spine. This paper shows that there exists a d-page book embedding of G in which each edge crosses the spine O(log_d n) times. As a direct corollary, for any real number s, there is an n^s -page book embedding of G in which each edge crosses the spine a constant number of times. In another paper, Enomoto-Miyauchi-Ota show that for an integer d, if n is sufficiently large compared with d, then for any embedding of K_n into a d-page book, there must exist Ω(n² log_d n) points at which edges cross over the spine. This means our result is the best possible for K_n in this case.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E83-A No.8 pp.1732-1734

Publication Date: 2000/08/25

Publicized

Online ISSN

DOI

Type of Manuscript: LETTER

Category: Graphs and Networks

Cite this

Copy

Miki Shimabara MIYAUCHI, "Trade off between Page Number and Number of Edge-Crossings on the Spine of Book Embeddings of Graphs" in IEICE TRANSACTIONS on Fundamentals, vol. E83-A, no. 8, pp. 1732-1734, August 2000, doi: .
Abstract: This paper studies the problem of book-embeddings of graphs. When each edge is allowed to appear in one or more pages by crossing the spine of a book, it is well known that every graph G can be embedded in a 3-page book. Recently, it has been shown that there exists a 3-page book embedding of G in which each edge crosses the spine O(log₂ n) times. This paper considers a book with more than three pages. In this case, it is known that a complete graph K_n with n vertices can be embedded in a n/2 -page book without any edge-crossings on the spine. Thus it becomes an interesting problem to devise book-embeddings of G so as to reduce both the number of pages used and the number of edge-crossings over the spine. This paper shows that there exists a d-page book embedding of G in which each edge crosses the spine O(log_d n) times. As a direct corollary, for any real number s, there is an n^s -page book embedding of G in which each edge crosses the spine a constant number of times. In another paper, Enomoto-Miyauchi-Ota show that for an integer d, if n is sufficiently large compared with d, then for any embedding of K_n into a d-page book, there must exist Ω(n² log_d n) points at which edges cross over the spine. This means our result is the best possible for K_n in this case.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e83-a_8_1732/_p

Copy

@ARTICLE{e83-a_8_1732,
author={Miki Shimabara MIYAUCHI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Trade off between Page Number and Number of Edge-Crossings on the Spine of Book Embeddings of Graphs},
year={2000},
volume={E83-A},
number={8},
pages={1732-1734},
abstract={This paper studies the problem of book-embeddings of graphs. When each edge is allowed to appear in one or more pages by crossing the spine of a book, it is well known that every graph G can be embedded in a 3-page book. Recently, it has been shown that there exists a 3-page book embedding of G in which each edge crosses the spine O(log₂ n) times. This paper considers a book with more than three pages. In this case, it is known that a complete graph K_n with n vertices can be embedded in a n/2 -page book without any edge-crossings on the spine. Thus it becomes an interesting problem to devise book-embeddings of G so as to reduce both the number of pages used and the number of edge-crossings over the spine. This paper shows that there exists a d-page book embedding of G in which each edge crosses the spine O(log_d n) times. As a direct corollary, for any real number s, there is an n^s -page book embedding of G in which each edge crosses the spine a constant number of times. In another paper, Enomoto-Miyauchi-Ota show that for an integer d, if n is sufficiently large compared with d, then for any embedding of K_n into a d-page book, there must exist Ω(n² log_d n) points at which edges cross over the spine. This means our result is the best possible for K_n in this case.},
keywords={},
doi={},
ISSN={},
month={August},}

Copy

TY - JOUR
TI - Trade off between Page Number and Number of Edge-Crossings on the Spine of Book Embeddings of Graphs
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1732
EP - 1734
AU - Miki Shimabara MIYAUCHI
PY - 2000
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E83-A
IS - 8
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - August 2000
AB - This paper studies the problem of book-embeddings of graphs. When each edge is allowed to appear in one or more pages by crossing the spine of a book, it is well known that every graph G can be embedded in a 3-page book. Recently, it has been shown that there exists a 3-page book embedding of G in which each edge crosses the spine O(log₂ n) times. This paper considers a book with more than three pages. In this case, it is known that a complete graph K_n with n vertices can be embedded in a n/2 -page book without any edge-crossings on the spine. Thus it becomes an interesting problem to devise book-embeddings of G so as to reduce both the number of pages used and the number of edge-crossings over the spine. This paper shows that there exists a d-page book embedding of G in which each edge crosses the spine O(log_d n) times. As a direct corollary, for any real number s, there is an n^s -page book embedding of G in which each edge crosses the spine a constant number of times. In another paper, Enomoto-Miyauchi-Ota show that for an integer d, if n is sufficiently large compared with d, then for any embedding of K_n into a d-page book, there must exist Ω(n² log_d n) points at which edges cross over the spine. This means our result is the best possible for K_n in this case.
ER -