On the Page Number of Lexicographic Product of Paths and Cycles in Books∗

ZHAO Bin,TIAN Yingzhi,MENG Jixiang

(College of Mathematics and System Sciences,Xinjiang University,Urumqi Xinjiang 830046,China)

Abstract: 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.

Key words:book embedding;page number;lexicographic product

0 Introduction

In this paper,we only consider simple connected and undirected graphs.For a graphG,we denote all vertices byV(G)and all edges byE(G).Abookconsists of aspinewhich is just a line and some number ofpageseach of which is a half-plane with the spine as boundary.A book embedding of a graphGconsists of placing the vertices ofGon the line in order and assigning edges of the graph to pages so that edges assigned to same page without crossing.Page number,denoted bypn(G),is a measure of the quality of a book embedding which is the minimum number of pages in whichGcan be embedded.An example in Fig 1 is helpful to understandpn(G).

Ollmann[1] first introduces the page number problem and that is NP-complete,even if the order of nodes on the spine is fixed[2,3].The book embedding problem has been motivated by several areas of computer science such as sorting with parallel stacks,single-row routing,fault-tolerant processor arrays and turning machine graphs[2].Book embeddings have applications in several contexts,such as VLSI design,fault-tolerant processing,sorting networks and parallel matrix multiplication[2,4–6].

The lexicographic product of two graphsGandH,denoted byG[H],is the graph with vertex setV(G)×V(H)and?(u1,v1),(u2,v2)?∈E(G[H])if and only if eitheru1u2∈E(G),oru1=u2andv1v2∈E(H).

Bernhart[7]gives an important theorem to fix the page number of some graphs.

Fig 1 Embedding of K4,pn(K4)=2.The ordering of V(G)is{v1,v2,v3,v4}.In(b),dashed line represents one page,black lines represent another

Theorem 1[7]LetGbe a connected graph.Then

(i)pn(G)=0 if and only ifGis a path;

(ii)pn(G)≤1 if and only ifGis outplanar;

(iii)pn(G)≤2 if and only if G is a subgraph of a Hamiltonian planar graph.

In next section,we will discuss the page number of lexicographic product of paths.

1 Page Number of Pm[Pn]

Theorem 2For positive integerm,pn(Pm[P2])=2.

ProofSincePm[P2]is a Hamilton planar graph,by Theorem 1,pn(Pm[P2])=2.

Theorem 3For positive integerm,pn(Pm[P3])≤4.

ProofWhenmis even,vertex ordering and edge embedding ofPm[P3]are shown in Fig 2.

Fig 2 Embedding of Pm[P3]with m is even

Whenmis odd,vertex ordering and edge embedding ofPm[P3]are shown in Fig 3.

Above all,for positive integerm,pn(Pm[P3])≤4.

By the de finition of the lexicographic product,for graphGandH,G[H]has ’layering’structure.Thats is to say:for a fixed vertexui∈V(G),letHibe the graph withV(Hi)={(ui,vj)|vj∈V(H)}and edge setE(Hi)=t=1,2,...,nand

Fig 3 Embedding of Pm[P3]with m is odd

Theorem 4For positive integermandn≥4,

ProofFirst,we give the vertex ordering ofPm[Pn].InPm[Pn],letPnibe a copy ofPnwithi∈{1,2,...,m}.SoIfiis odd,we de fine the ordering ofV(Pni)as{(i,1),(i,2),...,(i,n)}.Ifiis even,we de fine the ordering ofV(Pni)as{(i,n),(i,n−1),...,(i,1)}.Denote the ordering ofV(Pni)by σi.Then vertex ofPm[Pn]by the ordering:σ,σ,...,σ.ThusV(P[P])has an ordering already on spine,denoted by σ.

Case 1.1Ifm≥4 andnis even,for a certaini∈{1,2,...,(m−1)},andcan be embedded in one page,wheres∈{0,1,...,−1)}.Similarlyandcan be embedded in another page.Henceneedsnpages to be embedded.Fori1,i2∈{1,2,...,(m−1)},ifi1andi2are both even(or odd),edges inEiand edges inEido not cross.SoEican be embedded innpages,wherei∈{1,2,...,(m−1)}.If one ofi1andi1+1 is even and the other is odd,edges inEi1cross edges inEi1+1.Therefore,needs 2npages to be embedded.

Case 1.2Ifm≥4 andnis odd,for a certaini∈{1,2,...,(m−1)},we have thatandcan be embedded in one page,wherej∈{1,2},i∈{1,2,...,(m−1)andinn−1 pages.Forneeds one page to be embedded.Socan be embedded innpages.Similar to the proof of Case 1.1,ifnis odd,thenneeds 2npages to be embedded.

Case 2Ifm=3,similar to the proof ofm≥4,we have thatpn(Pm[Pn])≤2n.Fornis even,in ordering σ,edges indo not cross withSo for a certaintthe page number ofPm[Pn]can be reduced one page.Since edges inand edges incan be embedded in one page,whereThen we have the same result.Therefore,

Case 3Ifm=2,clearly,E1can be embedded innpages.

Above all,

2 Page Number of Pm[Cn]

Lemma 1LetGbe a spanning subgraph ofG0.Ifpn(G)=pin the ordering σ andE(G0)−E(G)can be embedded inlpages in the same vertex ordering,thenpn(G0)=porpn(G0)≤p+l.

ProofIn ordering σ,if any edgeei∈E(G0)−E(G)does not cross with every edge in some page ofGand there does not existej∈E(G0)−E(G)cross with it in this page,thenpn(G0)=p.If not,since edges inEcan be embedded inlpages,thenpn(G0)≤p+l.

Theorem 5For positive integern≥3,pn(P2[Cn])=3.

ProofBecauseP2[Cn]hasK5-minor,P2[Cn]is a nonplanar graph.From Theorem 1.1,pn(P2[Cn])≥3.On the other hand,we denote edges?(1,1),(n,1)?and?(2,1),(n,2)?bye1ande2.SoE(P2[Cn])=E(P2[Pn])∪e1∪e2.Sincee1ande2cross with edges inE(P2[Pn]),ande1does not cross withe2,from Theorem 2 and Lemma 1,pn(P2[Cn])≤3.Hencepn(P2[Cn])=3.

Theorem 6For positive integerm≥3,pn(Pm[C3])≤4.

ProofWe denote edgesPm[P3]in Theorem 3.In the ordering,anyeiandejdo not cross with each other,whereei,ej∈E.From Fig 2 and Fig 3,we observe that all edges inEcan be embedded in page-3 ofPm[P3].Therefore,we havepn(Pm[C3])≤4.

Similar to the Theorem 5,by Lemma 1,we have the next theorem.

Theorem 7For positive integerm≥3 andn≥4,pn(Pm[Cn])≤pn(Pm[Pn])+1.

3 Page Number of Cm[Pn]

Theorem 8For positive integerm≥3,pn(Cm[P2])≤4.

ProofThe book embedding ofCm[P2]is shown in Fig 4.

Fig 4 The book embedding of Cm[P2]

Theorem 9For positive integerm≥3,pn(Cm[P3])≤8.

Proof=E(Pm[P3])∪E0∪E1∪E2∪E3.Denote the ordering ofPm[P3]in Theorem 3 by σ.In the ordering,E0andE1can be embedded in one page.Edge setE2needs another page to be embedded.Since edges?(1,1),(m,3)?and?(1,3),(m,1)?cross with each other in σ,E3can be embedded in two pages.Therefore,four pages to be embedded.From Lemma 1,pn(C[P])=pn(P[P])+4≤8.

Theorem 10For positive integerm≥3 andn≥4,

ProofLetordering ofPm[Pn]in Theorem 4.From the proof of Theorem 4,we know thatEmcan be embedded innpages,and ifmis even,Emcan be embedded in some pages same withEi,whereiis even andi∈{1,2,...,(m−1)}.So ifmis even,pn(Cm[Pn])=pn(Pm[Pn]).Ifmis odd,edges inEmcross with edges inE1andEm−1.SoEmneeds another page to be embedded.So ifmis odd,pn(Cm[Pn])≤pn(Pm[Pn])+n.

4 Page Number of Cm[Cn]

Theorem 11For positive integersm≥3 andn≥3,pn(Cm[Cn])≤pn(Cm[Pn])+1.

ProofWe denote (i,1),(i,n)byeiandCm[Pn],ThenEonly needs one page to be embedded.By Lemma 1,we havepn(Cm[Cn])≤pn(Cm[Pn])+1.

5 Concluding

In this work,we give the upper bounds ofPm[Pn],Cm[Pn],Pm[Cn]andCm[Cn].For differentnandm,we have different results.In some conditions,we can determine the exact page number of these graphs.But due to the structure of lexicographic product of two arbitrary graphsGandHis very complex,we leave it for future study.