Topological Book Embedding of Bipartite Graphs

Miki MIYAUCHI

doi:10.1093/ietfec/e89-a.5.1223

Topological Book Embedding of Bipartite Graphs

Miki MIYAUCHI

Full Text Views

0

Cite this

Summary :

A topological book embedding of a graph is an embedding in a book that carries the vertices in the spine of the book and the edges in the pages so that edges are allowed to cross the spine. Recently, the author has shown that for an arbitrary graph G with n vertices there exists a d+1-page book embedding of G in which each edge crosses the spine log_dn times. This paper improves the result for the case of bipartite graphs and shows that there exists a d+1-page book embedding of a bipartite graph G_n₁,n₂ having two partite sets with n₁ and n₂ vertices respectively (n₁ ≥ n₂) in which each edge crosses the spine log_d n₂ -1 times.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E89-A No.5 pp.1223-1226

Publication Date: 2006/05/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1093/ietfec/e89-a.5.1223

Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

Category

Cite this

Copy

Miki MIYAUCHI, "Topological Book Embedding of Bipartite Graphs" in IEICE TRANSACTIONS on Fundamentals, vol. E89-A, no. 5, pp. 1223-1226, May 2006, doi: 10.1093/ietfec/e89-a.5.1223.
Abstract: A topological book embedding of a graph is an embedding in a book that carries the vertices in the spine of the book and the edges in the pages so that edges are allowed to cross the spine. Recently, the author has shown that for an arbitrary graph G with n vertices there exists a d+1-page book embedding of G in which each edge crosses the spine log_dn times. This paper improves the result for the case of bipartite graphs and shows that there exists a d+1-page book embedding of a bipartite graph G_n₁,n₂ having two partite sets with n₁ and n₂ vertices respectively (n₁ ≥ n₂) in which each edge crosses the spine log_d n₂ -1 times.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e89-a.5.1223/_p

Copy

@ARTICLE{e89-a_5_1223,
author={Miki MIYAUCHI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Topological Book Embedding of Bipartite Graphs},
year={2006},
volume={E89-A},
number={5},
pages={1223-1226},
abstract={A topological book embedding of a graph is an embedding in a book that carries the vertices in the spine of the book and the edges in the pages so that edges are allowed to cross the spine. Recently, the author has shown that for an arbitrary graph G with n vertices there exists a d+1-page book embedding of G in which each edge crosses the spine log_dn times. This paper improves the result for the case of bipartite graphs and shows that there exists a d+1-page book embedding of a bipartite graph G_n₁,n₂ having two partite sets with n₁ and n₂ vertices respectively (n₁ ≥ n₂) in which each edge crosses the spine log_d n₂ -1 times.},
keywords={},
doi={10.1093/ietfec/e89-a.5.1223},
ISSN={1745-1337},
month={May},}

Copy

TY - JOUR
TI - Topological Book Embedding of Bipartite Graphs
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1223
EP - 1226
AU - Miki MIYAUCHI
PY - 2006
DO - 10.1093/ietfec/e89-a.5.1223
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E89-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 2006
AB - A topological book embedding of a graph is an embedding in a book that carries the vertices in the spine of the book and the edges in the pages so that edges are allowed to cross the spine. Recently, the author has shown that for an arbitrary graph G with n vertices there exists a d+1-page book embedding of G in which each edge crosses the spine log_dn times. This paper improves the result for the case of bipartite graphs and shows that there exists a d+1-page book embedding of a bipartite graph G_n₁,n₂ having two partite sets with n₁ and n₂ vertices respectively (n₁ ≥ n₂) in which each edge crosses the spine log_d n₂ -1 times.
ER -