A book embedding of a graph G consists of placing the vertices of G on a spine and assigning edges of the graph to pages so that edges assigned to the same page without crossing.In this paper
we discuss book embedding of lexicographic product of paths and cycles
and give upper bounds of the page number of these graphs.Specially
in some conditions
we can determine the exact page number of these graphs.
关键词
Keywords
references
Ollmann L T.On the book thicknesses of various graphs[C]//Hoffman,Levow,T EDS Proc 4th southeastern conference on combinatorics,Graph theory and computing,Congressus Numerantium,Winnipeg:Utilitas Mathematics Publ Inc,1973.VIII 459.
Chung F R K,Leighton F T,Rosenberg A L.Embedding graph in books:a layout problem with applications to VLSI design[J].SIAM J Alg Disc Meth,1987,8(1):33-58.
Shahrokhi F,Shi W.On crossing sets,disjiont sets and pagenumber[J].J Algorithms,2000,34(1):40-53.
Rosenberg A L.The Diogenes approach to testable fault-tolerant arrays of processors[J].IEEE T Comput,1983,32(10):902-910.
Heath L S,Leighton F T,Rosenberg A L.Compariting queues and stacks as mechanisms for laying out graphs[J].SIAM J Discrete Math,1992,5(3):398-412.
Tarjan R E.Sorting using networks of queues and stacks[J].JACM,1972,19(2):341-346.
Bemhart F,Kainen B.The book thickness of a graph[J].J Comb Theory B,1979,27(3):320-331.