home lbeaudou home fourier these articles bokal crossing rapport IF klein bottle 09 25

Informations

• Publié par: Inyo
• Nombre de lectures: 21
• Langue: English

Extrait

Institut

Fourier

Institut Fourier

Unit´eMixtedeRecherche5582 CNRS–Universit´eJosephFourier

On the sharpness of some results relating cuts and crossing numbers

1 2 Laurent Beaudou and Drago Bokal

16f´evrier2009

On the sharpness of some results relating cuts and crossing numbers

1 2 Laurent Beaudou and Drago Bokal

1 Institut Fourier 100, rue des Maths 38402StMartind’H`eres–FRANCE 2 Faculty of Natural Science and Mathematics University of Maribor Maribor – SLOVENIA

laurent.beaudou@ujfgrenoble.fr drago.bokal@unimb.si

Abstract/Re´sum´e

It is already known that given two graphs together with two coherent bundles in each graph, the crossing number of the zipproduct of these graphs is greater than the sum of the crossing numbers of the graphs. When the size of the cut between the zipped graphs is at most two, just one bundle in each graph suffices for the inequality. In this paper, we prove that such a relaxed condition is not sufficient when the size of the cut is at least four, and we prove that the difference can grow quadratically with the cut size. Keywords:crossing number, zipproduct, graph cut

Etantdonn´esdeuxgraphescontenantdeuxbundlescohe´rents,onsaitparun the´ore`medudeuxie`meauteurquelenombredecroisementsduproduitzipp´e des deux graphes est plus grand que le la somme des nombres de croisements dechaquegraphe.Danscetravail,nousre´pondonsn´egativement`alaquestion naturelledelane´cessite´decesdeuxbundlesdanschaquegraphe.Deplus,nous exhibonsunefamilledegraphere´alisantunediffe´rencearbitrairementgrande entrecesdeuxquantite´s Motscle´s:crossing number.

1

Introduction

Crossing number of graphs (see [11] for basic definitions) has been extensively studied for about thirty years and is still a notorious problem in graph theory. While determining or bounding the crossing number of graphs used to be the main issue at the beginning, the focus is now shifting to structural aspects of the crossing number problem. These include the study of several variants of crossing number [5, 7, 15, 16, 18, 19], crossingcritical graphs [8, 20, 21], or the properties of drawings with a bounded number of crossings per edge [17]. Very early at the development of the crossing number theory Leighton re alized that cuts in graphs play an important role in determining the crossing number of a graph. Combining them with the LiptonTarjan planar separator theorem [14], he used edge cuts in graphs to provide upper bounds on cross ing numbers [1], whereas in the bisection method [12, 13], he used this fact to provide lower bounds for the crossing number. Both the upper and the lower bound arising from graph cuts are rather gen eral methods, but neither provides the sharpness needed to yield exact bounds. This issue was resolved by the introduction of the zip product of graphs in [2, 3], which led to exact crossing number of several twoparameter graph fam ilies, most general being the crossing number of the Cartesian product of any subcubic tree with any starK 1,n family includes, as a subfamily, the. This product of any path and any star, resolving a longstanding conjecture by Jen ´ ˇ drolandScˇerbovain[10].Besides,ithasalsobeenhelpfulforotherworks concerning exact crossing numbers (as in [22, 23]), but also regarding crossing critical graphs (see [4, 9]). It is natural to ask about its behaviour with respect to graph invariants. The zip product approach, however, assumes a technical condition of having two coherent bundles in the zipped graphs (we formalize this condition later). In this paper, we examine the possible weakenings of this condition and prove that having only one bundle in each graph is not sufficient to establish superaditivity of crossing number with regard to the zip product. Moreover, we are able to achieve any gap between both quantities and show that the gap can grow quadratically with the number of edges involved in the zip product. In the first section, we state definitions of zip product and bundles and recall precedent results. In the second part, we describe the families of graphs that we use in the proof of our main result.

2

The zip product

Fori= 1,2, letG i be a graph andv i ∈V(G i ) such that bothv 1 andv 2 have same degreed. LetN i =N G i (v i ) be the set of neighbouring vertices ofv i in G i , and letσ:N 1 →N 2 We callbe a bijection. σazip functionof the graphs G 1 andG 2 at verticesv 1 andv 2 . Thezip productofG 1 andG 2 according toσ is the graphG 1 ⊙ σ G 2 obtained from the disjoint union ofG 1 −v 1 andG 2 −v 2 after adding edgesuσ(u) for anyu∈N 1 . Letv∈V(G) be a vertex of degreedinG. Abundleofvis a setBofd edgedisjoint paths fromvto some vertexu∈V(G),u6=v. Vertexvis the sourceof the bundle anduis itssinkvertices on the paths of. Other Bare ˘ internal verticesof the bundle. LetE(B) =E(B)∩E(G−v) denote the set of

3

edges of bundles The

Bthat are not incident withv. They are B 1 andB 2 ofvarecoherentif their sets following result was established in [3]:

calleddistant edgesofB. Two of distant edges are disjoint.

Theorem 2.1(Bokal [3])Fori= 1,2, letG i be a graph,v i ∈V(G i )a vertex of degreed, andN i =N G i (v i ). Also assume thatv i has two coherent bundles B i,1 andB i,2 inG i . Then,cr(G 1 ⊙ σ G 2 )≥cr(G 1 ) + cr(G 2 )for any bijection σ:N 1 →N 2 .

Note that, as stated above, the zip product is defined to involve vertices that have no incident multiple edges. However, the reader shall have no difficulty establishing the same result for graphs with multiple edges: if the edges in each multiple edge are subdivided, the crossing number is preserved and the resulting graph is simple. The zip product is done using these simple graphs. If necessary, we can suppress the degreetwo edges after the zip product, and obtain back the multiple edges.

3

Two families of graphs

We define two families of graphs with specific crossing number, such that in each a chosen vertex has a single bundle.

Definition 3.1Given any integern≥4, letn= 4k+r. LetK=K 2,4 with bipartitiona i ,i= 1,2andb j ,j= 1,2,3,4. The graphH k,r is obtained fromK with the following steps:

1. adding a cycleC=b 1 b 2 b 3 b 4 , 2. subdividing the edgea 1 b i withx i ,i= 1,3, 3. adding the edgex 1 x 3 , 4. replacing every edge withkparallel edges,

5. addingrmore edges to the multiedgesa i b 4 ,i= 1,2.

Figure 1(a) depictsH 3,1 .

2 Lemma 3.2Fork≥1andr∈ {0,1,2,3},cr(H k,r ) =k.

Proof.It is easy to find a subdivision ofK 3,3 inH 1,r , thus cr(H 1,r )≥1. Figure 1(a) gives a natural way of drawingH 1,0 with 1 crossing, establishing 2 2 cr(H 1,0 Furthermore, it is obvious that cr() = 1. H k,0 ) =kcr(H 1,0 ) =k. Since H k,0 is a subgraph ofH k,r , we have cr(H k,r )≥cr(H k,0 the other hand,). On one can alter an optimal drawing ofH k,0 to a drawing ofH k,r with the same 2 number of crossings (as in Figure 1(a), concluding cr(H k,r ) = cr(H k,0 ) =k.

Definition 3.3Given any integern≥4, letn= 4k+r. LetK=K 2,4 with bipartitiona i ,i= 1,2andb j ,j= 1,2,3,4graph. The G k,r is obtained fromK with the following steps:

1. adding a cycleC=b 1 b 2 b 3 b 4 ,

4

b 4

b 3

x 3

a 1

a 2

b 2

(a) GraphH 3,1

x 1

b 1

b 4

x 3 y 3 b 3

a 1

a 2

x 1 y 1 b 2

(b) GraphG 3,1

Figure 1: Two families of graphs:G k,r andH k,r

2. subdividing the edgea 1 b i twice, withx i ,y i ,i= 1,3,

3. adding the edgesx 1 y 3 andx 3 y 1 ,

4. replacing every edge withkparallel edges,

5. addingrmore edges to the multiedgesa i b 4 ,i= 1,2.

Figure 1(b) depictsG 3,1 .

2 Lemma 3.4Fork≥1andr∈ {0,1,2,3},cr(G k,r ) = 2k.

b 1

Proof.The subgraphG 1,0 contains a subdivision of a graph, obtained from K 3,4 by splitting two vertices of degree 4. This graph has crossing number two [6], and the drawing in Figure 1(b) gives a way of drawingG 1,0 establishing 2 2 cr(G 1,0 ) = 2. By construction, cr(G k,0 ) =kcr(G 1,0 ) = 2k. Furthermore, it is easy to modify the optimal drawing ofG k,0 to a drawing ofG k,r with the same number of crossings as in Figure 1(b). AsG k,r hasG k,0 as a subgraph, we have 2 cr(G k,r ) = cr(G k,0 ) = 2k.

4

The Zip Product Gap

Proposition 4.1LetG 1 ,G 2 be graphs,v i ∈V(G i )of degreedhas one bundle B i inG i ,σa bijection among neighborhoods ofv i . If there exists an optimal drawingDofG 1 ⊙ σ G 2 , such that no edge ofG 1 −v 1 crosses an edge ofG 2 −v 2 , thencr(G 1 ⊙ σ G 2 )≥cr(G 1 ) + cr(G 2 ).

Proof.Without loss of generality we may assume thatG i ,i= 1,2 are con nected. Due to the bundles,G i −v i are connected, too. LetD i be obtained from D[(G i −v i )∪B 3−i ] by contracting any of its faces whose boundary contains only

5

segments of edges ofB 3−i . ThenD i is a drawing ofG i , with the contracted region representing the vertexv i . Clearly, each crossing ofD i appears inD, thus cr(G 1 ⊙ σ G 2 ) = cr(D)≥ cr(D 1 ) + cr(D 2 )≥cr(G 1 ) + cr(G 2 ).

The following theorem establishes that in general, one bundle at each vertex used in the zip product does not suffice for preservation of the crossing number: Theorem 4.2For anyn≥4, there exist graphsG 1 ,G 2 , such thatG i has a vertexv i with a bundle inG i ,d G i (v i ) =n, andcr(G 1v 1 ⊙ v 2 G 2 )<cr(G 1 ) + cr(G 2 ). Proof.Letn= 4k+rand setG 1 =H k,r ,G 2 =G k,r , and letv i ,i= 1,2, 2 be the vertexa 1 from the definition of the respective graph. Then cr(G 1 ) =k, 2 cr(G 2 ) = 2k.

(a)G 1,1 ⊙H 1,1

(b) Better drawing ofG 1,1 ⊙ H 1,1

Figure 2:G 1,1 ⊙H 1,1

2 2 The drawing in Figure 2(b) establishes cr(G 1v 1 ⊙ v 2 G 2 )≤2k <3k= cr(G 1 ) + cr(G 2 ).

Combining Theorem 4.2 with Proposition 4.1, we obtain the following: Corollary 4.3For anyn≥4, there exist graphsG 1 ,G 2 , such thatG i has a vertexv i with a bundle,d G i (v i ) =n, andG 1 −v 1 crossesG 2 −v 2 in any optimal drawing ofG 1v 1 ⊙ v 2 G 2 . Let graphsG 1 andG 2 bencompatible, if eachG i contains a vertexv i of degreen, such thatv i has a bundle inG i . Define g(nmax [cr() = G) + cr(G)−cr(G⊙G)], 1 2 1v 1 v 2 2 G 1 ,G 2

6

where the maximum runs over allncompatible pairsG 1 ,G 2 . Theorem 4.2 establishes the following corollary:

2 Corollary 4.4Letg(n)Thenbe defined as above. g(n) = Ω(n).

The proof of

Thus, we have a lower bound on the possible crossing number gap between the two original graphs and their zip product in terms of the size of the edge cut between the zipped graphs. An upper bound, on the other hand, is far from clear, as the edges of the two bundles can possibly cross each other arbitrarily often in the optimal drawing of the zip product, and optimal drawings of the original graphs can have different structure than the corresponding subdrawings of optimal drawings of the zipped graph. We summarize this discussion in the following problem:

2 Problem 4.5Find an upper bound ong(n). Isg(n) =O(n)?

Theorem 2.1 establishes that if the vertices involved in the zip product have two coherent bundles, then the crossing number is preserved. On the other hand, Theorem 4.2 establishes that whenever their degree is at least four, just one bundle at each vertex is not enough. Therefore, two natural problems remain open:

Problem 4.6LetG 1 ,G 2 be graphs, such thatG i has a vertexv i with a bundle inG i andd G i (v i ) = 3. Iscr(G 1v 1 ⊙ v 2 G 2 )≥cr(G 1 ) + cr(G 2 )?

Problem 4.7LetG 1 ,G 2 be graphs, such thatG i has a vertexv i withd G i (v i ) = dthat. Assume v 1 has two coherent bundles inG 1 , butv 2 has just one bundle inG 2 . Iscr(G 1v 1 ⊙ v 2 G 2 )≥cr(G 1 ) + cr(G 2 )?

References

[1] S. N. Bhatt and F. T. Leighton, A framework for solving VLSI graph layout problems,J. Comput. System Sci.28(1984), 300–343.

[2] D. Bokal, On the crossing number of Cartesian products with paths,J. Combin. Theory Ser. B97(2007) 381–384.

[3] D. Bokal, On the crossing numbers of Cartesian products with trees,J. Graph Theory56(2007) 287–300.

[4] D. Bokal, Infinite families of crossingcritical graphs with prescribed av erage degree and crossing number, to appear inJ. Graph Theory.

[5] D. Bokal, G. Fijav and B. Mohar, The minor crossing number,SIAM J. Disc. Math.20(2006) 344–356.

[6] D. Bokal, B. Oporowski, R. B. Richter and G. Salazar, Characterization of 2crossingcritical graphs I: Low connectivity or noV 8 minor, in prepa ration. ˇ [7]E.Czabarka,O.Sy´kora,L.A.Sze´kelyandI.Vrto,Biplanar crossing numbers I: a survey of results and problems, preprint, http://www.math.sc.edu/ szekely/survey4.pdf.

7

[8]P.Hlineˇn´y,Crossingcriticalgraphshaveboundedpathwidth,J. Combin. Theory Ser. B88(2003), 347–367.

[9]P.Hlineˇny´,Newinfinitefamiliesofcrossingcriticalgraphs,Electronic J. Combin.15(2008), R102. ´ ˇ [10]S.JendrolandM.Sˇcerbova,OnthecrossingnumberofS m ×P n and ˇ S m ×C n ,Cas. Pest. Mat.107(1982) 225–230. [11]M.Kleˇsˇc,ThecrossingnumberofK 2,3 ✷C 3 ,Discrete Math.251(2002) 109–117.

[12] F. T. Leighton,Complexity Issues in VLSI, MIT Press, Cambridge, 1983.

[13] F. T. Leighton, New lower bound techniques for VLSI,Math. Systems Theory17(1984), 47–70.

[14] R. Lipton and R. Tarjan, A separator theorem for planar graphs,SIAM J. Appl. Math.36(1979), 177–189.

[15] B. Mohar, The genus crossing number, submitted.

[16]J.PachandG.T´oth,Degeneratecrossingnumbers,InAmenta and: N. O. Chedong, eds.Proceedings of the twentysecond annual symposium on Computational geometry255–258., ACM, New York, 2006:

[17]J.PachandG.T´oth,Graphsdrawnwithfewcrossingsperedge,Combi natorica17(1997), 427–439.

[18]J.PachandG.T´oth,Whichcrossingnumberisitanyway?,J. Combin. Theory Ser. B80(2000), 225–246.

[19] M. J. Pelsmajer, M. Schaefer and D. tefankovi, Odd Crossing Number Is Not Crossing Number,InHealy and N. S. Nikolov, eds.,: P. Graph th Drawing:13International Symposium, Lecture Notes in Comput. Sci. 3843386–396., Springer, Berlin, 2006:

[20] R. B. Richter and C. Thomassen, Minimal graphs with crossing number at leastk,J. Combin. Theory Ser. B58(1993), 217–224.

[21] G. Salazar, Infinite families of crossingcritical graphs with given average degree,Discrete Math.271(2003), 343–350.

[22] Tang Ling, Lu Shengxiang and Huang Yuanqiu, The Crossing Number of Cartesian Products of Complete Bipartite GraphsK 2,m with PathsP n , Graphs Combin.23(2007) 659–666.

[23] Zheng Wenping, Lin Xiaohui and Yang Yuansheng, The crossing number ofK 2,m ✷P n ,Discrete Math.308(2008) 6639–6644.

8