Topological Book Embedding of Bipartite Graphs(<Special Section>Discrete Mathematics and Its Applications)

スポンサーリンク

概要

• 論文の詳細を見る

• 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_d n] 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_<n1,n2> having two partite sets with n_1 and n_2 vertices respectively (n_1≥n_2) in which each edge crosses the spine [log_d n_2]-1 times.

• 一般社団法人電子情報通信学会の論文
• 2006-05-01

著者

• MIYAUCHI Miki

  NTT Communication Science Laboratories, NTT Corporation

関連論文

• (d+1,2)-Track Layout of Bipartite Graph Subdivisions
• Queue Layout of Bipartite Graph Subdivisions(Discrete Mathematics and Its Applications)
• Topological Book Embedding of Bipartite Graphs(Discrete Mathematics and Its Applications)

スポンサーリンク