UNIVERSITY OF LJUBLJANA FACULTY OF MATHEMATICS AND PHYSICS DEPARTMENT OF MATHEMATICS Drago Bokal Structural Approach to the Crossing Number of Graphs Doctoral Thesis ADVISER: Prof. Dr. Bojan Mohar Ljubljana, 2006 UNIVERZA V LJUBLJANI FAKULTETA ZA MATEMATIKO IN FIZIKO ODDELEK ZA MATEMATIKO Drago Bokal Strukturni pristop k prekrižnemu številu grafov doktorska disertacija MENTOR: prof. dr. Bojan Mohar Ljubljana, 2006 Abstract Crossing-critical graphs were introduced by Siran, who proved existence of infinite families of 3-connected fc-crossing-critical graphs for every k > 3. Kochol proved existence of infinite families of simple 3-connected fc-crossing-critical graphs, k > 2. Richter and Thomassen started the research on degrees in crossing-critical graphs by proving that there are only finitely many simple fc-crossing-critical graphs with minimum degree r for every two integers r > 6 and k > 1. Salazar observed that their argument implies the same conclusion for every rational r > 6, integer k > 1, and simple fc-crossing-critical graphs with average degree r. For every rational r G [4, 6) he proved existence of an infinite sequence {fcr,i}L0 such that for every % G N there exists an infinite family of simple 4-connected fc^-crossing-critical graphs with average degree r and asked about existence of such families for rational r G (3, 4). The question was partially resolved by Pinontoan and Richter, who answered it positively for r G (3|, 4). In the present work we extend the theory of tiles, developed by Pinontoan and Richter, to encompass a generalization of the crossing-critical graphs constructed by Kochol. Combining tiles with a new graph operation, the zip product, which preserves the crossing number of the involved graphs, we settle the question of Salazar and combine the answer with the results of Siran and Kochol into the following theorem: there exists a convex continuous function / : (3,6) -»¦ R+, such that, for every rational number r G (3,6) and every integer k > /(r), there exists an infinite family of simple 3-connected crossing-critical graphs with average degree r and crossing number k. Beineke and Ringeisen investigated the crossing numbers of Cartesian products of small graphs with cycles and established the crossing numbers of the Cartesian product of Cn D G where G is any simple graph of order four, except the 3-star, K1>3. Jendrol’ and ˇčerbova closed this gap and also obtained the crossing number of Pm D K1>3. They conjectured the general result for Pm D K1>n, which was proven for 'n = 4 by Kleˇsˇc. We prove their conjecture in a slightly more general setting: by combining the result of Asano about the crossing number of KlAn with the zip product, we establish the crossing number of T D K1>n where'T is any tree of maximum degree three and n > 3 vii is any integer. We supplement this result by the crossing number of T D K1>3 for any tree T, the crossing number of Pm D Wn for any m > 1, n > 3, and some other exact results and bounds. Seymour regretted that the crossing number does not work well with graph minors, as the contraction of an edge can both increase and decrease the value of this graph invariant. We introduce the minor crossing number, a minor-monotone graph invariant that allows for further minimization of the number of crossings by allowing replacement of vertices by trees and minimizing the number of crossings in the resulting graph. We argue that this graph invariant is more natural in the VLSI applications than the ordinary crossing number, prove several general lower bounds on the minor crossing number, study the structure of graphs with bounded minor crossing number and provide some exact results and bounds for specific graphs. In particular, we generalize a result of Moreno and Salazar, who bounded the crossing number of a graph from below using the crossing number of its minor of small maximum degree. Math. Subj. Class. (2000): 05C62 Graph representations (geometric and intersection representations, etc.), 05C10 Topological graph theory, imbedding, 05C83 Graph minors. Keywords: crossing number, crossing-critical graph, average degree, Cartesian product, star, path, tree, wheel, minor crossing number, graph minor. Povzetek Raziskovanje prekrižno-kritičnih grafov je začel Širan, ki je za vsak cel k > 3 konstruiral neskončno družino 3-povezanih fc-prekrižno-kritičnih grafov. Ko-chol je za vsak cel k > 2 konstruiral neskončno družino enostavnih 3-povezanih fc-prekrižno-kritičnih grafov. Richter in Thomassen sta začela s študijem stopenj vozlišč v prekrižno-kritičnih grafih, ko sta pokazala, da za vsaka cela r > 6 in k > 1 obstaja le končno mnogo fc-prekrižno-kritičnih grafov z minimalno stopnjo r. Salazar je opazil, da iz njunega argumenta sledi obstoj le končno mnogo fc-prekrižno-kritičnih grafov s povprečno stopnjo r za vsak cel k > 1 in vsak racionalen r > 6. Pokazal je, da za vsak racionalen r G (4, 6) obstaja tako zaporedje {fcr,i}t~0> da za vsak i G N obstaja neskončna družina krr prekrižno-kritičnih grafov s povprečno stopnjo r, in vprašal po obstoju takih družin za r G (3,4). Na vprašanje sta delno pozitivno odgovorila Pinontoan in Richter, ki sta razvila teorijo tlakovcev in z njeno pomočjo konstruirala iskane družine za r G (3±, 4). V disertaciji nadgradimo njuno delo, da omogoči posplošitev prekrižno-kritičnih grafov, ki jih je konstruiral Kochol. Kombinacija teorije tlakovcev in nove operacije na grafih in njihovih risbah, šiva, nam omogoči popoln odgovor na Salazarjevo vprašanje in njegovo povezavo z rezultati Širana in Kochola v obliki naslednjega izreka: obstaja taka zvezna konveksna funkcija / : (3,6) -»¦ R+, da za vsako racionalno število r G (3,6) in vsako celo število k > f(r) obstaja neskončna družina prekrižno-kritičnih grafov s povprečno stopnjo r in prekrižnim številom k. Beineke in Ringeisen sta raziskovala prekrižno število kartezičnih produktov malih grafov in ciklov ter določila natančne vrednosti za vse Cn D G, kjer je G poljuben graf reda štiri, razen 3-zvezda K1>3. JendroP in Ščerbova sta zapolnila to vrzel. Ugotovila sta tudi prekrižno število Pm D K1>3 in postavila domnevo za splošen rezultat o Pm D K1>n. Domnevo je za n = 4 dokazal Klešč. V nekoliko splošnejši različici jo za vsak n > 3 dokažemo v pričujočem delu: rezultat Asana o prekrižnem številu grafa K1>3>n povežemo z operacijo šiv in dobimo prekrižno število grafa T D K1>n, kjer je T poljubno drevo z maksimalno stopnjo tri in n > 3 poljubno celo število. Ta rezultat dopolnimo s prekrižnim številom grafov T D K1>3 za poljubno drevo T, prekrižnim številom ix grafov Pm D Wn za poljubna m > 1, n > 3, ter več drugimi eksaktnimi rezultati in mejami. Seymour je obžaloval, da prekrižno število ne sodeluje na naraven način s teorijo grafovskih minorjev: stiskanje povezave lahko vrednost te invariante poveča ali zmanjša. V tem delu uvedemo minorsko prekrižno število. To je minorsko monotona invarianta, ki omogoča dodatno zmanjševanje števila križišč v risbi, tako da vozlišča zamenjamo z drevesi in minimiziramo število križišč v risbah vseh takih grafov. Ta invarianta ima bolj naravne uporabe pri izdelavi elektronskih vezij kot navadno prekrižno število. V delu pokažemo več splošnih mej za njeno vrednost, raziščemo strukturo grafov z omejenim minorskim prekrižnim številom in predstavimo nekaj eksaktnih rezultatov in mej za posamezne družine grafov. Ena od spodnjih mej je posplošitev rezultata Morene in Salazarja, ki sta prekrižno število grafa omejila s prekrižnim številom njegovega minorja z majhno maksimalno stopnjo. Math. Subj. Class. (2000): 05C62 Predstavitve grafov (geometrijske predstavitve, predstavitve s preseki itd.), 05C10 Topoloˇska teorija grafov, vloˇzitve, 05C83 Grafovski minorji. Ključne besede: prekrižno število, prekrižno-kritičen graf, povprečna stopnja, kartezični produkt, zvezda, pot, drevo, kolo, minorsko prekrižno število, grafovski minor. I implore my memory to reach back, to seize all doubts and despairs, all hopes and passions, all dreams and funerals, all prophecies and disappointments, all the killed, crippled and wounded, desecrated, all exalted on altars and wrapped in flags, all intoxicated by happiness and sobered from sorrow, let me remember all weepings and jubilations, all funny stories and loves, all sins, all leaps into the unknown, all fires, floods, earthquakes and God’s commandments, let all the tender fragile ties that bind body and soul, me and someone else, be revealed, let me perceive all conceptions and gentle abandons, all the shameful confessions and states of purity, let the remembrances of all these vibrate inside me and my surroundings, and let me be included in the collective guilt and the collective absolution. I, thus, request to be able to keep neighbors in front of and behind me, be the middleman of messages from the future even though they at times are strange, incomprehensible, threatening or calming, brief or tedious. It is probable that none of us fully understands the whole game, but courage itself is absolute and all-knowing. Edvard Kocbek, 1977 There were many who helped me in my partial understanding of the game. The mother, the father, the sister, the brother, the relatives, the friends, the teachers, the professors, and others. Their trust gave wind to the wings of my thoughts, their doubts challenged me to look deeper and sharpen the arguments. Some of them are closely related to this work. Bojan Mohar, the supervisor, was with it from the very beginning. He found a balance between encouragement and doubt, strengthened with patience. The weekly meetings of the Graph Theory Workshop he led in Ljubljana were of high value to an apprentice. Gaˇsper Fijavˇz introduced me to crossing number problems at a conference in Koˇsice. In Star´a Lesn´a, Mari´an Kleˇsˇc pointed out a problem that later turned out to be easily accessible with the developed tools. Bruce Richter and Gelasio Salazar not only developed the fundament on which this work was built, but also expressed interest in it at a stimulating meeting in Waterloo, just prior the text was written up. Matt DeVos, always willing for a mathematical debate, had several terminological suggestions. Deborah Kent took time to improve on the English. Andrej Vodopivec, together with Deborah, Matt, and the Mohar family, made the stay in Burnaby, where the work has been completed, an enjoyable experience. Franziska Berger was the inspiration to many of the thoughts in the thesis. To all, my sincerest thanks. Prosim, da bi mi spomin segel daleč nazaj in obsegel vse dvome in obupe, vsa upanja in zanose, vse sanje in pogrebe, vse prerokbe in razočaranja, vse ubite, pohabljene in ranjene, oskrunjene, vse na oltar povzdignjene in v zastave ovite, blazne od sreče in trezne od nesreče, naj se spomnim vseh jokov in vriskov, vseh smešnic in ljubezni, vseh grehov, vseh skokov v neznano, vseh požarov, povodnji, potresov in božjih zapovedi, naj si odkrijem vse nežne nitke, ki vežejo telo in dušo, mene in bližnjika, naj si predočim vsa spočetja in blage sprostitve, vsa sramotna priznanja in vsa čista stanja, vsega tega naj se spomnim v sebi in v svoji okolici, predvsem pa naj se vključim v skupno krivdo in v skupno odvezo. Prosim torej, da bi se še dalje držal soseda pred seboj in soseda za seboj in sprejemal poročila od spredaj in jih predajal nazaj, čeprav so včasih tuja, nerazumljiva, preteča ali pomirljiva, kratka in naporna. Morda nihče med nami ne razume igre do kraja, vendar je drznost brezpogojna in vsevedna. Edvard Kocbek, 1977 Mnogo jih je bilo, ki so mi pomagali pri iskanju razumevanja igre. Mati, oče, sestra, brat, sorodniki, prijatelji, učitelji, profesorji in drugi. Njihovo zaupanje je dalo poleta mojim zamislim, njihovi dvomi so izzvali globlji pogled in izostritev argumentov. Nekateri od njih so tesno povezani s tem delom. Bojan Mohar, mentor, je bil z njim od vsega začetka. Našel je ravnovesje med spodbudo in dvomom, utrjeno s potrpežljivostjo. Tedenska srečanja Grafovske delavnice, ki jo je vodil v Ljubljani, so bila dober poduk za vajenca. Gašper Fijavž mi je na konferenci v Košicah predstavil prekrižno število grafov. V Stari Lesni je Marian Klešč izpostavil problem, ki se je kasneje izkazal za lahko dostopnega z izdelanimi orodji. Bruce Richter in Gela-sio Salazar sta ne le zgradila temelje, na katerih sloni to delo, ampak tudi izkazala zanimanje zanj na spodbudnem srečanju v Waterlooju tik pred pisanjem besedila. Matt DeVos, vedno pripravljen na matematični razgovor, je imel več terminoloških predlogov. Deborah Kent si je vzela čas za izboljšavo uporabljene angleščine. Andrej Vodopivec je skupaj z Deborah, Mattom in družino Moharjevih poskrbel, da je bil čas v Burnabyu, kjer je bilo delo dokončano, prijetna izkušnja. Franziska Berger je bila navdih mnogim mislim v disertaciji. Vsem iskrena hvala. Contents Abstract vii Povzetek ix I The Crossing Number 1 Introduction 3 1 Graphs and their drawings 5 1.1 Graphs ................................ 5 1.1.1 Basic definitions ....................... 5 1.1.2 Families of graphs ...................... 7 1.1.3 Graph minors ........................ 8 1.2 Drawings ............................... 9 1.2.1 Embeddings of graphs on surfaces ............. 9 1.2.2 Drawings of graphs and the crossing number ....... 10 2 Resultsonthe crossing number 13 2.1 Historic overview .......................... 13 2.2 General bounds ........................... 15 2.3 Exact results ............................ 18 2.4 Crossing-critical graphs ....................... 21 2.5 Applications ............................. 23 2.6 Contribution of this thesis ..................... 25 II Crossing-critical Graphs 29 3 Zip product 31 3.1 Definition and basic lemmas .................... 31 3.2 Homogeneity condition ....................... 35 xvii 4 Tiles 39 4.1 Definition and basic lemmas .................... 39 4.2 Properties of tiles .......................... 41 4.3 Gadgets in tiles ........................... 43 4.3.1 Twisted pairs ........................ 44 4.3.2 Staircase strips ....................... 45 4.3.3 Cloned vertices ....................... 50 4.3.4 Wheel gadgets ........................ 51 4.3.5 Other gadgets ........................ 52 5 Constructions 55 5.1 Average degree three ........................ 55 5.2 Average degree six ......................... 57 5.3 Adapting graphs .......................... 59 5.4 Infinite families ........................... 60 5.5 Structure of crossing-critical graphs ................ 62 6 Cartesian products 65 6.1 General graphs ........................... 65 6.2 Cycles ................................ 67 6.3 Stars ................................. 68 6.4 Wheels ................................ 69 III The Minor Crossing Number 73 7 Preliminaries 75 7.1 Definitions and basic lemmas ................... 76 7.2 Cubic realizing graphs ....................... 77 8 Bounds 79 8.1 Using the maximum degree .................... 79 8.2 Using the genus ........................... 81 8.3 Using the connected components ................. 83 9 Structure of graphs with bounded mcr(G,?) 85 9.1 Systems of curves .......................... 86 9.2 Structure theorem .......................... 87 9.3 Improved bound ........................... 89 10 Applications 91 10.1 Complete graphs .......................... 91 10.2 Complete bipartite graphs ..................... 93 10.3 Hypercubes ............................. 94 10.4 Cartesian products of cycles .................... 96 Bibliography 97 Indexofterms 109 Indexofsymbols 115 Razˇsirjeni povzetek 117 Definicije ............................... 117 Prispevek disertacije k teoriji prekriˇznega ˇstevila ......... 118 Prekriˇzno-kritiˇcni grafi ....................... 121 Karteziˇcni produkti ......................... 133 Minorsko prekriˇzno ˇstevilo ..................... 135 XX Part I The Crossing Number 1 Introduction In his 1917 book, Amusements in Mathematics, Henry Ernest Dudeney published the following problem [28]: There are some half-dozen puzzles, as old as the hills, that are perpetually cropping up, and there is hardly a month in the year that does not bring inquiries as to their solution. Occasionally one of these, that one had thought was an extinct volcano, bursts into eruption in a surprising manner. I have received an extraordinary number of letters respecting the ancient puzzle that I have called “Water, Gas, and Electricity.” It is much older than electric lighting, or even gas, but the new dress brings it up to date. The puzzle is to lay on water, gas, and electricity, from W, G, and E, to each of the three houses, A, B, and C, without any pipe crossing another. Take your pencil and draw lines showing how this should be done. You will soon find yourself landed in difficulties. A contemporary graph-theoretical view of the problem provides a simple proof that the puzzle has no solution: it is asking for a planar embedding of the complete bipartite graph K3,3, which does not exist due to the Euler Formula. This puzzle is to our knowledge the first appearance of the problem of minimizing the number of crossings in a drawing. Although the origins of this problem can be traced back to recreational mathematics, it turns to be quite difficult and has attracted considerable attention of modern mathematicians, including Tur´an, Erd˝os, and Tutte. The bounds on the minimum number of crossings in a drawing of a graph on a surface, called the crossing number, have been applied in several areas of mathematics. In this thesis we study two structural approaches to the crossing number invariant. After the introductory Part I we investigate crossing-critical graphs in Part II and the minor crossing number in Part III. In the first part we introduce the terminology and notation in Chapter 1 and review the results on the crossing number in Chapter 2. The second part contains solutions to two previously open problems. In it, we study the crossing-critical graphs, which are minimal graphs with the 3 4 crossing number above some predefined bound and thus give insights into the structural behavior of this graph invariant. In Chapter 3 we define a new graph operation, the zip product, which can preserve the crossing number and the criticality of the involved graphs. Chapter 4 builds upon the theory of tiles of Pinontoan and Richter, which we augment with a general construction of crossing-critical graphs and with some new gadgets that are used to establish lower bounds on the crossing numbers of graphs. The tools designed in these two chapters are applied in Chapter 5, where we settle a question of Salazar, and discuss the new insights these tools provide into the structure of crossing-critical graphs. The zip product also has applications in studies of the crossing numbers of Cartesian products of graphs, which we present in Chapter 6. There ˇ we settle a conjecture of Jendrol’ and Sˇcerbov´a. Connections between the theory of graph minors and the crossing number are studied in the third part of this thesis. In Chapter 7 we introduce a new minor-monotone graph invariant, the minor crossing number, and establish some of its basic properties. This invariant allows us to apply the techniques of graph minors in the study of the crossing minimization problem. In Chapter 8 we present some general bounds for the minor crossing number and in Chapter 9 we discuss the structure of graphs with bounded value of this graph invariant and apply the results to improve the previously obtained bounds. We conclude the study of the minor crossing number by establishing some exact results and bounds for several classical families of graphs in Chapter 10. Chapter 1 Graphs and their drawings In this chapter, we define the mathematical framework and the notation that will be used in subsequent chapters. We assume familiarity with basics of Graph Theory [27] and related Topology of Surfaces [85]. Also, some arguments have an algebraic flavor [52]. The respective references provide sufficient background for these topics. 1.1 Graphs 1.1.1 Basic definitions A graph G is a structure consisting of two sets: V(G) are the vertices of G and E(G) are the edges of G. Each edge e connects precisely two endvertices uandv, which is denoted by e = uv. The endvertices need not be distinct, and an edge whose endvertices are equal is called a loop. An edge is incident with its endvertex and vice versa. Two endvertices of the same edge are adjacent, as well as two edges sharing an endvertex. Adjacent vertices are neighbors of each other. For a vertex v G V(G) we denote with NG(v) = {u G V(G) | uv G E(G)} its neighborhood in G. We also define the multiplicity neighborhood NG(v), which is the multiset that contains each neighbor uofv with multiplicity of the edge uv in E(G). Then the degree of v in G equals the size of NG(v), degG(w) = \NG(v)\. The maximum and minimum degree of a graph G are denoted by ?(G) and 5(G), respectively. A graph is d-regular if all its vertices have degree d. Graphs with maximum degree three are called subcubic graphs and 3-regular graphs are called cubic graphs. A graph can have multiple edges but not loops, for reasons discussed in Section 1.2.2. When loops are present, we employ the term multigraph. A graph that has neither loops nor multiple edges is a simple graph. 5 6 Graphs and their drawings We call a vertex v E V(G) a dominating vertex of G if it is adjacent to every other vertex in G. A vertex cover of G is a set S of vertices of G, such that each edge of G is incident with some vertex in S. Let d and G2 be two graphs and

k + 1 and G - S is connected for any set S C F(G), |S| < fc. Similarly, we define k-edge-connected for 5 C L(G). A vertex v E V(G) or an edge e G L(G) is a cutvertex (cutedge) if {v} ({e}) is a separator in G. Two edges e,/ G E(G) are in the same block of G if they are equal or 1.1 Graphs 7 if there exists a cycle C in G with e, f E E(C). This is another equivalence relation; the subgraphs spanned by the equivalence classes are called blocks of G. For a graph G we define its block graph H as follows: the set of vertices V(H) contains all the cutvertices and blocks of G, and the set of edges of H contains precisely all the edges of the form vB where v is a cutvertex, B a block, and v G V(B). Proposition 1.1 ([27]). The block graph H of any graph G is a forest. H is connected if and only if G is connected. Let Gi, G2 be two subgraphs of G. The intersection GlC\G2 is the subgraph of G, having the vertices V(GX) n V(G2) and the edges E(GX) n E(G2). Let Gi, G2 be two disjoint graphs. Their disjoint union GlUG2 has vertices V(Gi)U V(G2) and edges E(G1)\JE(G2). Their join Gx+G2 is obtained from GiUG2 by nr Gi, G2 be two disjoint graphs. Their disjoint union G1l)G2 has vertices V(Gi)U JG2by adding all the edges of {m; | u G V(Gi),t; G V(G2)}. Their Cartesian product Gi D G2 has vertices V(Gi) x V(G2); two vertices (u^v) and (u2,t;2) are adjacent if and only if uxu2 G E(GX) or wiw2 G E(G2). Complement Gc of a (simple) graph G is the simple graph on vertices V(G) in which two vertices are adjacent if and only if they are not adjacent in G. Line graph L(G) of G is the graph whose vertices are E(G) and two of them are adjacent if and only if they share a vertex in G. Let e = uv be an edge of a graph G. A subdivision of e results in the graph obtained from G by replacing e in G with a new vertex w adjacent precisely to u and w. A graph H is a subdivision of G if it is obtained from G by a sequence of subdivisions of edges. In such case, we also say that G and H are homeomorphic graphs. Let u G V(G) be a vertex of degree three with neighbors x,y,z. The Y ?-transformation of G at m is the graph obtained from G-v after adding the edges xy, yz, and zx. Conversely, if xy, yz, and zx are three edges (a triangle) in G, then the ?Y-transformation of G at the triangle xyz is the graph obtained from G - {xy, yz, zx} by adding a new vertex t; and the edges xv, yv, and zv. A k-coloring of vertices of G is a mapping c : V(G) -»¦ {1,..., fc} that assigns different colors to adjacent vertices. A k-edge-coloring is defined similarly. The chromatic number X(G) of a graph G is the smallest number k for which a fc-vertex coloring of G exists. The chromatic index X'(G) of G is the smallest k for which a fc-edge-coloring of G exists. 1.1.2 Families of graphs In this section we define several particular families of graphs used throughout the thesis. The complete graph Kn is the graph with vertices V(Kn) = 8 Graphs and their drawings {v1}..., vn} and edges E(Kn) = {viVj | 1 < % < j < n}, i.e. it contains an edge between any pair of distinct vertices. The empty graph Kn is the complement of Kn: it has n vertices V(Kn) = {v1}..., vn} but no edges. The complete bipartite graph Km,n has vertices partitioned into two sets A = {ux,... ,um}, B = {vu...,vn}, V(Km,n) = Al)B, and has all possible edges between vertices of these sets: E(Km,n) = {mvj | 1 < i < m, 1 < j < n}. The n-star Sn is the complete bipartite graph K1>n. We have already defined the path Pm and the cycle Cm. The wheel Wn is the join of the cycle Cm with the graph Kx. The hypercube of dimension d is the graph Qd whose vertices are strings of length d over the alphabet {0,1}. Two such strings are adjacent in Qd if and only if they differ in precisely one position. An alternative definition is Qd = K2 D K2 D ¦¦¦UK2 with precisely d factors K2. 1.1.3 Graph minors Let e = uv be an edge of a graph G that is not a loop. The contraction of e results in the graph G/e in which the edge e is removed and the vertices u and v are identified into a new vertex. In the context of graph minors, we forbid removal of cutedges of G. Thus, cut-edges can only be contracted and loops can only be removed. A graph G is a minor of a graph H if G can be obtained from a subgraph of H by a sequence of edge-contractions. We denote this relationship by G 0, and nonorientable surfaces Nc, c > 1, where §fc denotes the 2-sphere with h handles and Nc denotes the 2-sphere with c crosscaps. The number h is the orientable genus of §fc and c is the nonorientable genus of Nc. Some particular surfaces we consider are the torus §u the projective plane Ni, and the Klein bottle N2. An embedding of a graph G in a surface S consists of two mappings ( k and cr(G -e,E) < k for any edge e E E{G). A graph is crossing-critical in E if it is fc-crossing-critical for some k. A rectilinear drawing is a drawing of a simple graph G in the plane, E2, in which the image of any edge is a straight line segment. The rectilinear crossing 1.2 Drawings 11 number rcr(G) is the smallest number of crossings in any rectilinear drawing of G in the plane. Loops do not affect the crossing number of graphs: we can always draw them in a small neighborhood of the vertex without any crossings. Thus, a graph with a given crossing number can have arbitrarily many loops, and a crossing-critical graph contains none. 12 Graphs and their drawings Chapter 2 Results on the crossing number In this chapter, we review significant results on the crossing number. First, we outline the historic development of the topics in Section 2.1. Then, we concentrate on general crossing number bounds in Section 2.2 and on exact results in Section 2.3. Next, we continue with an overview of results on crossing-critical graphs in Section 2.4 and applications of the crossing number invariant in mathematics and engineering in Section 2.5. Finally, we conclude with the contribution of this thesis to the knowledge about crossing numbers in Section 2.6. 2.1 Historic overview In 1930, Kuratowsky characterized planar graphs as the graphs that contain neither a K3,3 nor a K5 subdivision [74]. This result was followed in 1934 by Chojnacki, who established planarity of any graph that has a plane drawing in which no pair of edges crosses an odd number of times [24]. In the present terminology, this result states that any graph with odd crossing number equal to zero is planar. Many years later, Tutte proved this result in his attempt to create algebraic foundations for the theory of crossing numbers [131]. The module over the set of pairs of edges that he created made the proof clearer, but was applied only in few other results [124]. Tur´an asked about the smallest number of crossings of rail tracks between kilns and storage places [130]. In graph theoretical formulation, he was interested in the crossing number of the complete bipartite graph Km,n. This initial question already demonstrated all the fallaciousness of the crossing number problems: in 1952 Tur´an presented the problem to Zarankiewicz, who claimed to have solved it in 1954 [137]. However, a fault in the proof was discovered by Kainen and Ringel and described by Guy [47], who also conjectured the cross- 13 14 Results on the crossing number ing number of complete graph Kn. Until today, both problems were solved only in some special cases (cf. Section 2.3). After the 1950s, the research on crossing numbers continued in various directions. Some of it was dedicated to finding or estimating crossing numbers of graphs, cf. Sections 2.2 and 2.3. There were also attempts to characterize properties of graphs with given crossing number. The result of Kuratowsky characterizes graphs with crossing number zero in terms of forbidden subdivisions, but for larger crossing numbers no such general results are known. Kulli, Akka and Beineke characterized line graphs with crossing number one [73]. Bloom, Kennedy and Quintas conjectured that a graph with crossing number at least two contains a subgraph with crossing number equal to two [17]. Several special cases of this conjecture were proven by Richter [99], who also established that every cubic graph with crossing number at least two contains a subdivision of one of eight graphs [98], which extends a similar result of Glover and Huneke [43] for cubic graphs that do not embed in the projective plane. A complementary result of McQuillan and Richter states that every cubic 2-crossing-critical graph has crossing number equal to two [81]. This relates to crossing-critical graphs, which were first defined in [17]. As they are one of the main topics of this thesis, we devote them more space in Section 2.4. Garey and Johnson opened the algorithmic aspect of the crossing number by showing that the question cr(G) ? k is NP-complete [40]. Their transformation to the optimal linear arrangement problem uses multigraphs with high multiplicity of edges and high vertex degree. Recently, Hlinˇeny´ improved upon their transformation to the optimal linear arrangement problem by using simple cubic graphs [55]. The result is that the crossing number problem is NP-complete already for cubic graphs. For a fixed value of k, the problem turns to be polynomial (i.e. the crossing number problem is fixed-parameter tractable). A na¨ive algorithm that runs in time O(m2k+1) chooses k pairs of edges, subdivides each of them, identifies the two new vertices of every pair, and checks whether the new graph is planar. Significantly better theoretically, but still inappropriate for application, is the fairly recent algorithm of Grohe that answers cr(G) ? k in quadratic time for fixed k [45]. The algorithm uses bounded treewidth of crossing-critical graphs to compute a monadic second-order logic formula, which can be evaluated in linear time. Buchheim, Ebner, J¨unger, Klau, Mutzel, and Weiskircher have developed an algorithm that allows exact crossing minimization for sparse graphs of order less than 40 [22]. For realistic applications to graphs of higher order, we have to rely on approximations of the crossing number. Drawings of a bounded degree graph G of order n with O(log2 n(cr(G)+n)) crossings can be obtained by combining algorithms of Bhatt and Leighton [13] with those of Chung and Yau [25], cf. [116]. 2.2 General bounds 15 Some attention has also been devoted to drawings of graphs respecting specific constraints and to various heuristics; references can be found in [132]. Let us conclude this historic overview with another controversy about crossing numbers. In Section 1.2.2, we introduced two versions of the crossing number invariant: the ordinary and the rectilinear crossing number. However, there can be more: one could count just the number of pairs of edges that cross (the pair crossing number), or count just those pairs of edges that cross an odd number of times (the odd crossing number). According to [100], the problem of seemingly mismatching definitions was first pointed out by Mohar in Burlington, Vermont, in 1995. Pach and T´oth described the problem in [92], where they observed that the result of Chojnacki [24] and Tutte [131] states that odd crossing number zero implies planarity. When these discrepancies were revealed, distinctness of the rectilinear crossing number and the ordinary one was already known: for any prescribed crossing number k > 4 Bienstock and Dean exhibited families of graphs with arbitrarily high rectilinear crossing number [14] and showed that for graphs of bounded maximum degree the rectilinear crossing number is bounded by a function of the degree and the ordinary crossing number [15]. Pach and T´oth proved that the ordinary crossing number of a graph is bounded from above by two times the square of the odd crossing number. They also extended some results about the crossing number to the odd crossing number. Recently Pelsmajer, Schaefer, and ˇ tefankoviˇc showed that the odd crossing number of a graph can be different from the pair crossing number and thus from the ordinary one [94]. They designed graphs for which odd crossing number does not exceed (^ + o(1)) cr(G). 2.2 General bounds During the study of the crossing number, three general lower bounds for the value of this invariant have emerged. They can all be traced back to Leighton’s pioneering work on applications of crossing number in VLSI design [76]. We review these results in the present section. The most straightforward general lower bound for the crossing number of a simple graph follows from the Euler Formula: if the graph has too many edges, then it cannot be planar and each excessive edge must cross some other. The Crossing Lemma uses this fact and boosts it with a probabilistic argument: Theorem 2.1 (The Crossing Lemma). Let G be a simple graph with n vertices and m edges, m ? 4n. Then, 16 Results on the crossing number Proof. Let D be an optimal drawing of G. We may assume that no pair of edges crosses twice in D and that adjacent edges do not cross. The graph of D is thus a simple graph with cr(G) + n vertices and 2 cr(G) + m edges. The Euler Formula implies 3(cr(G) + n)-6>m + 2 cr(G), i.e. cr(G) > m - 3n + 6. (2.1) Let D' be a random induced subdrawing of D, obtained by choosing each vertex of G with probability p. Let ri,m',d denote the random variables, respectively representing the number of vertices, edges, and crossings of D'. Inequality (2.1) holds for any drawing and we infer that d > m'-3n'. The same holds for the expected values of these variables. These are easy to compute: EM) = pn, E(m') = p2m, and E(c') = pA cr(G). By setting p = ^ we obtain cr(G) > m 3m ^2 ~^' cr(G) > m3 3m3 16n2 64n2 cr(G) > m3 64n2- D This bound, with a general constant c in place of ^, was conjectured by Erdos and Guy in 1973 [34]. It was proven by Leighton [76] and independently by Ajtai, Chv´atal, Newborn and Szemeredi [4] for c = ^ in 1982. The above proof emerged in an email communication between Chazelle, Sharir, and Welzl and is featured in The Book [3]. The result has several interesting applications outside Graph Theory, cf. Section 2.5. The constant has been improved first by Pach and T´oth [91] and then by Pach, Radoiˇcic, Tardos, and T´oth [88]. Currently, the strongest version of the Crossing Lemma is the following: Theorem 2.2 ([88]). The crossing number of any simple graph G on n vertices and m edges satisfies 1 to3 cr G >---------- - 1.06ra. ( ) ~ 31.1 n2 Ifm>±fn, then 1024 to3 cr(G) ž 31827T? 2.2 General bounds 17 The key improvement, which provides additional advantage over the above stated proof, is improving the bounds implied by the Euler Formula. The authors achieve this by studying drawings of sparse graphs in which every edge is crossed a bounded number of times. Pach, Spencer, and T´oth generalized the Crossing Lemma to graphs satisfying certain monotone graph properties in [90]. Specifically, they examined high girth and forbidden complete bipartite subgraphs. They also investigated behavior of graphs with super-linear, sub-quadratic number of edges and proved the following: Theorem 2.3 ([90]). If n < e < n2, then define for simple graphs G and K(n,e)= min cr (G) n(G) = n e(G) = e C= lim K(n,e)^. ri—> oo 1TI, The limit C exists and C > 0. Moreover, the limit C is the same for every the surface in which we consider the crossing number. Another general lower bound on the crossing number of a graph G employs an embedding f of some other graph H, \V(H)\ < \V(G)\, into G: f maps vertices of H into vertices of G and edges of H into paths between corresponding vertices in G. For this reason, it is called the embedding method [116]. The edge congestion /if counts the maximum number of such paths running through an edge of G and the vertex congestion mf a maximum number of paths through a vertex. Using these concepts, Shahrokhi and Szekely prove the following: Theorem 2.4 ([119]). Let G be a graph of order n and f an embedding of a graph H into G. Then, cr(G)>^-^V. This method, like the other two, can be applied to the crossing number in any orientable or nonorientable surface. The advantage is that it can be applied to multigraphs. The definitions, proofs, and some extensions can be found in [116, 117, 119]. The method generalizes an earlier work of Leighton, who used 18 Results on the crossing number embeddings of Kn to estimate the crossing numbers of shuffle-exchange graphs and meshes of trees [76]. The bisection method is the third general method for bounding the crossing numbers of graphs that we describe. The bisection width of a graph G is the smallest number of edges between two vertex subsets of G, each of which contains at least one third of the vertices of G. The method was first applied by Leighton, who showed the following using the planar separator theorem by Lipton and Tarjan [78]: Theorem 2.5 ([76]). Let G be a simple graph of order n and bounded maximum degree. Then, cr(G) + n=?(b2), where b is the bisection width ofG. This theorem was sharpened by Pach, Shahrokhi, and Szegedy to use particular vertex degrees of G [89]. Sykora and Vrto extended the bisection method to surfaces of higher genus [120]. 2.3 Exact results The lower bounds discussed in Section 2.2 usually provide at most a correct order of magnitude of the crossing number of the graph in question, but are of little use when exact values need to be known. These are often hard to determine and standard methods do not exist. For some highly symmetric graphs, they are obtained using ad hoc arguments. The results can roughly be divided into four groups: the study of complete, complete bipartite, and similar graphs; the study of Cartesian products, in particular hypercubes and Cartesian products of two cycles; the study of generalized Petersen graphs; and the recent study of circulant graphs. All these graphs exhibit high levels of symmetry, which is used essentially in the arguments. As mentioned in Section 2.1, the problem of the crossing numbers of complete and complete bipartite graphs roots in the very beginning of the theory of crossing numbers. The topic is dominated by the following two conjectures: Conjecture 2.6 ([137]). Let n,m>3 be integers. Then, n\ \n — 1 I \m\ \ m — 1 2 2 ~2 cr(Xm)=|-|| —I l-l 1^1 m,n 2 2 2 2 Conjecture 2.7 ([47]). Let n > 5 be an integer. Then, n — 1 I I 77. — 2 I I 77. — 3 I 2 2 2 cr (Kn) = - 2.3 Exact results 19 Conjectured optimal drawings of Km,n were designed by Zarankiewicz [137] and of Kn by Blaˇzek and Koman [16], but their optimality is confirmed only for small values of parameters by Guy [46]. For Kn, these are cr(Kn) = 0 for n < 4, cr(K5) = 1, cr(K6) = 3, cr(K8) = 9, cr(K9) = 18, and cr(K10) = 36. Recently, Pan and Richter announced an extension to the next two values of n: cr(Kn) = 100 and cr(K12) = 150 [93]. For n < 10, Guy and Hill determined the crossing number of the complement of C„, which is the complete graph Kn with a Hamilton cycle removed [48]. For complete bipartite graphs, the known results date back to 1971, when Kleitman [65] confirmed Conjecture 2.6 for all n and 3 < m < 6. Later, Woodall [134] designed a computer based proof for 7 < m < 8 and 7 < n < 10. Asano established a related result: the crossing number of K1>3>n and K2An [10]. Richter and Thomassen studied the asymptotics and showed that the asymptotic validity of the conjectured result for Kn,n would imply the asymptotic validity for Kn [107]. The crossing numbers of complete and complete bipartite graphs were also studied on higher surfaces [60, 117]. The only exact results are the toroidal crossing number of Kn for n < 10 by Guy, Jenkins, and Schaer [50], and the crossing number of K3,n in any surface by Richter and Siran [104], who generalized the corresponding result of Guy and Jenkins for the torus [49]. Eggleton and Guy first studied the crossing numbers of hypercubes [30]. They found an error in the announced result - which came as no surprise to the crossing number theory - and the upper bound cr(Qd) < ^4ra - ^±± 2n~2 became a conjecture [34]. The first proven upper and lower bounds were established by Madej [80]. Using the embedding method, Sykora and Vrto obtained cr(Qd) = ?(4d) in [121], and their lower bound is the best known to date. Madej’s upper bound was first improved by Faria and Figueiredo [36]. Recently, Faria, Figueiredo, Sykora, and Vrto described a drawing that establishes the upper bound conjectured by Erdos and Guy in [34]: Theorem 2.8 ([37]). cr(Qd) < ^4ra - l^bi I 2n~2 for d>3. Dean and Richter proved the only nonplanar exact result known [26]: Q4 is isomorphic to C4 D C4 and has crossing number eight. Another view of the crossing numbers of hypercubes also attracted some interest. Kainen observed that if the genus of the surface in which Qd is drawn is allowed to vary, then the crossing numbers seem independent of d [61]. More precisely, if ? is a surface of genus g(Qd) - k and k < min{g(Qd), 2d~4} is a nonnegative integer, then 4fc < cr(Qd, ?) < 8k. Kainen and White proved a similar result for Qd D K4A in [62], which Pica, Pisanski, and Ventre generalized to Qd D K44 D G for bipartite graphs G of maximum degree d + 1 [97]. 20 Results on the crossing number The aforementioned result of Dean and Richter intersects the study of cubes with that of another difficult family of graphs: the Cartesian product Cm D Cn. The best drawing of these graphs is easy to obtain, but determining its optimality proved to be a hard problem. Harary, Kainen, and Schwenk proved cr(C3 D C3) = 3 in 1973 and conjectured cr(Cm D Cn) = (to - 2)n for 3 < m < ra [51]. For m = 3, this was proven by Ringeisen and Beineke using induction and an auxiliary Lemma stating that if no triangle has a crossed edge in some drawing of C3 D Cn, then the drawing has at least n crossings [108]. This paper already announces the result for m = 4, which was published in [12]. The proof examines distinct types of crossings and combines a careful partition of edges with an induction on n as the main tool. The topic was put aside for a decade and a half, until Kleˇsˇc and, independently, Richter and Stobert established the conjecture for m = 5 in [71]; Richter and Salazar for m = 6 in [102]; and Adamsson and Richter for m = 7 in [2]. All of them relied on the induction as the main tool. In all of the cases m = 3, 4, 5, 6, 7, the base case n = m was published separately [51, 26, 106, 5, 6], with the proof for C4 D C4 appearing in [26] only after the result was used. The recent state-of-the-art on the problem is the result of Glebsky and Salazar: Theorem 2.9 ([42]). cr(Cm D Cn) = (to - 2)n for m > 3 and n > \(m + 1)(to + 2). The result relies on several insightful ideas developed prior to this paper: Richter and Thomassen established the lower bound for the crossing numbers of drawings of Cm D Cn with both families of principal cycles pairwise disjoint [106] and Salazar extended this to drawings with just one family pair-wise disjoint [110]. The latter result was strengthened by Juarez and Salazar and applied to show half of the conjectured value as the best known general lower bound [58]. For 5 < m < n < § (to - 1), the best lower bound \mn was obtained by Shahrokhi, Sykora, Szekely, and Vrto [118]. They also proved lower bounds in the projective plane and in the Klein bottle. In their proof of Theorem 2.9, Juarez and Salazar applied the theory of arrangements introduced by Adamsson [1] and Adamsson and Richter [2], which they extended by a different assignment of crossings to the principal cycles. There was also a substantial amount of research done on other Cartesian products besides hypercubes and Cm D Cn. Beineke and Ringeisen determined the crossing number of G D Cn for any graph G of order 4, except S3 = K1>3 [12]. This gap was bridged by Jendrol’ and ˇčerbova, who determined the crossing number of S3 D C„, S3 D Pm, and S4 D P2 and conjectured the following: Conjecture 2.10 ([57]). cr(Sra D Pm) = (m-1) [f J [^J for n > 3, m > 1. 2.4 Crossing-critical graphs 21 Kleˇsˇc proved this conjecture for n = 4 and m ? 1 in [66], where he also determined cr(S4 D Cm) for m ? 3. In [70], he determined the crossing number of G D Pm and G D Sn for any graph G of order four and, in [67], the crossing number of G D Pm for any graph G of order five. For several graphs of order five, the crossing numbers of their Cartesian product with Cn or Sn are also known, as well as some other Cartesian products, most of which are due to Kleˇsˇc [66, 67, 68, 69, 71]. The methods rely on the high degree of symmetry that these Cartesian products exhibit and mostly apply the following approach: if no copy of G has a sufficient amount of crossings, then enough crossings can be found in the drawing, otherwise the claim follows by induction. Also, a carefully chosen partition of edges of the Cartesian product in question is usually applied. Generalized Petersen graphs form another family of graphs whose crossing numbers were studied. Already in 1981, Exoo, Harary, and Kabell showed cr(P(2fc + 1,2)) = 3 for k ? 3 by observing that these graphs contain a subdivision of P(7, 2) and by showing that this graph has crossing number three [35]. Since the other possibilities can be easily obtained, cr(P(n, 2)) is known for n ? 3. Fiorini has claimed to have established the crossing number of P(8,3) and subsequently P(3fc + 2,3), but later some doubt was shed on this result [39]. McQuillan and Richter simplified the proof for P(8, 3) in [82] and later Richter and Salazar corrected an error in Fiorini’s induction and established the crossing number of P(n, 3) for all n ? 9 in [103]. For general graphs P(n, k), only the upper and lower bounds are known [114]. Another family of graphs that exhibits rich symmetry are circulant graphs and their crossing numbers have recently attracted attention from various authors. Yuansheng, Xiaohui, Jianguo, and Xin established cr(C(ra, {1,3})) = LfJ + (n mod 3), n ? 8, in [135] and cr(C(3fc, {1, k})) = k, k ? 3, in [136]. Ma, Ren, and Lu established cr(C(2m + 2,m)) = m + 1, m ? 3, in [79]. Also recently, the crossing numbers of some of fractal-like Sierpin´ski graphs were established by Klavˇzar and Mohar [64]. Their structure and symmetry required aid of involved algebraic arguments. To conclude this section, we note that the asymptotics of many of the above families could be studied using the theory of tiles of Pinontoan and Richter, which we introduce later. Examples are demonstrated in [95]. 2.4 Crossing-critical graphs Crossing-critical graphs give insight into structural properties of the crossing ˇ number invariant and have thus generated considerable interest. Sir´anˇ introduced crossing-critical edges and proved that any such edge e of a graph G 22 Results on the crossing number with cr(G - e) < 1 belongs to a Kuratowsky subdivision in G [127]. Moreover, such a claim does not hold for edges with cr(G - e) > 5. In [128], Siran constructed the first infinite family of 3-connected fc-crossing-critical graphs for arbitrary given k > 3. Kochol [72] constructed the first infinite family of simple 3-connected fc-crossing-critical graphs (fc > 2). Richter and Thomassen proved the following: Theorem 2.11 ([105]). cr(G) < § k + 16 for a k-crossing-critical graph G. This result was used to prove the first in a sequence of results on vertex degrees in simple crossing-critical graphs. Theorem 2.12 ([105]). Let k > 1 and r > 6 be integers. There are only finitely many simple k-crossing-critical graphs with minimum degree r. Richter and Thomassen constructed an infinite family of simple 4-regular 4-connected 3-crossing-critical graphs and posed a question about existence of simple 5-regular fc-crossing-critical graphs. Salazar observed that their argument can be extended to the average degree: Theorem 2.13 ([111]). Let r > 6 be a rational number and k > 0 an integer. There are only finitely many simple k-crossing-critical graphs of average degree r. Since the finiteness of the set of simple 3-regular fc-crossing-critical graphs can be established using Robertson-Seymour graph minor theory, it follows that the only average degrees for which an infinite family of simple fc-crossing-critical graphs could exist are r G (3, 6]. Salazar constructed an infinite family of simple fc-crossing-critical graphs with average degree r for any r G [4, 6) and posed the following question: Question 2.14 ([111]). Let r be a rational number in (3,4). Does there exist an integer k and an infinite family of (simple) graphs, each of which has average degree r and is k-crossing-critical? Question 2.14 was partially answered by Pinontoan and Richter [96]. They proposed constructing crossing-critical graphs from smaller pieces or tiles, and applied this idea to design infinite families of simple fc-crossing-critical graphs for any prescribed average degree r G (3|,4). Salazar improved the factor f in Theorem 2.11 to 2 for large fc-crossing-critical graphs [112] and for graphs of minimum degree four [113]. Other structural results on crossing-critical graphs are the following theorem and corollary by Hlineny: 2.5 Applications 23 Theorem 2.15 ([53, 54]). There exists a function f such that no k-cros-sing-critical graph contains a subdivision of a binary tree of height f(k). In particular, k-1< f(k) < 6(72 log2 k + 248)fc3. Corollary 2.16 ([54]). Let f be the function from Theorem 2.15. If G is a k-crossing-critical graph, then the path-width of G is at most 2/W+1 - 2. Existence of a bound on the path-width of fc-crossing-critical graphs was first conjectured by Geelen, Richter, Salazar, and Thomas in [41], where they established a result implying a bound on the tree-width of fc-crossing-critical graphs. Hlineny defined crossed k-fences, which are fc-crossing-critical graphs, in [53]. Crossed fc-fences from some particular family contain subdivisions of binary trees of height k - 1 and thus have path-width at least 2k - 2. Focus of the research on crossing-critical graphs was on 3-(edge)-connect-ed crossing-critical graphs. This condition eliminates vertices of degree two that are trivial with respect to the crossing number. But the condition is much stronger and its application was justified only recently by the following structural result of Leanos and Salazar: Theorem 2.17 ([75]). Let G be a connected crossing-critical graph with minimum degree at least three. Then there is a collection Gl}... ,Gm of 3-edge-connected crossing-critical graphs, each of which is contained as a subdivision in G, and such that cr(G) = E™i cr(Gi). 2.5 Applications In this section, we review applications of the crossing number invariant. They include Very Large System Integration (VLSI), approximation, discrete geometry, additive number theory, measure theory, and linguistics. Leighton was the first to apply crossing number arguments to VLSI design [76]. He proposed several approaches to lower bounds for the crossing number (cf. Section 2.2), which he showed to have impact in the design of electronic circuits via the following two theorems: Theorem 2.18. Given a drawing D for a n-node graph G with c crossings it is possible to construct a layout for G with area at most 0((c + n) log2(c + n)). Theorem 2.19. Any circuit that computes a n-variable transitive Boolean function in time T = o(y/n) must have at least c wire crossings, where cT 2 > ?(n2). 24 Results on the crossing number Theorem 2.18 shows that it is worth finding drawings of graphs with few crossings. Also, one can translate lower bounds on the area of graph layouts (drawings) into lower bounds for the crossing number. Theorem 2.19 shows that graphs of fast circuits will have high crossing numbers. Further applications of the crossing number in VLSI amount mostly to obtaining good layouts of various graphs. Bhatt and Leighton designed a general algorithm for this purpose [13]. Leighton provided lower bounds on the area and the maximal edge-length of several layouts in [77]. Sykora and Vrto established a lower bound on the crossing numbers of arrangement graphs [122] as Chockalingam did for star-connected cycles [23]. Regarding approximation, recent results of Bodlaender and Grigoriev show that several polynomial time approximation schemes for planar graphs can be extended to graphs, embeddable in some surface with only few crossings per edge [18]. These include approximation schemes for the maximum independent set problem, the minimum vertex cover problem, and the minimum dominating set problem. Applications of the crossing number were introduced into discrete geometry through the following theorem of Szemeredi and Trotter. The original proof of this theorem was simplified by Szekely using the Crossing Lemma: Theorem 2.20 ([125],[126]). The maximum number I(n,m) of incidences between n points and m straight lines of the real plane satisfies I(n, m) = 0(n2/3m2/3 + n + m). Proof. We may assume that each line is incident with at least one point. Let G be the graph whose vertices are the n points in which two of them are adjacent if they lie consecutively on the same line. Let D be the drawing of G in which vertices are represented by the corresponding points and edges are drawn as straight line segments between them. Each of the m lines crosses at most m- 1 others, thus cr(G) < cr(D) < m2. Each line has one incidence with a point more than there are edges drawn on it, thus there are m incidences more than there are edges in G. Now the claim follows: either \E(G)\ < 4n or Theorem 2.1 implies m2 > cr(G) > ^{J^. ? Szekely applied Theorem 2.1 in a similar way and obtained several other counting results in discrete geometry, including the following improvement of the previously best known exponent f: Theorem 2.21 ([125]). Given n points in the plane, one of them determines at least en4/5 distinct distances from the others. The theorem of Szemeredi and Trotter was applied to establish several bounds in additive number theory. Through these applications, the crossing number relates to the following results: 2.6 Contribution of this thesis 25 Theorem 2.22 ([31]). There is a constant c> 0 such that the following holds for every set A of size n containing real numbers: en5/4 < max{\A + A\, \A-A\}. Theorem 2.23 ([33]). There is a positive constant c, such that en5/4 <\A + A~l\ for every set A of real numbers of size n. Other results of a similar flavor are surveyed in [32]. Perhaps the most astonishing is the following application of the crossing number in measure theory. Let /i be a probability distribution in the plane such that the probability of three //-randomly chosen points be collinear equals zero and let p(p) be the probability that four //-randomly chosen points form a convex quadrilateral. In 1865, Sylvester asked about the infimum of p(p) over all uniform distributions over open sets F with finite Lesbesgue measure [123]. Only an approximation was known for the restricted case of convex F, until Scheinerman and Wilf showed the following: Theorem 2.24 ([115]). Let p* = infp(p), where p runs over all probability distributions p such that the probability of three /i-randomly chosen points be collinear equals zero and let c* = lim^«, rcr"if°. Then, p* = c*. () At the time of writing it is known that 0.37553 < c* < 0.3838. The lower bound is due to Balogh and Salazar [11] and the upper bound due to Brodsky, Durocher, and Gethner [21]. We conclude with an application that relates the crossing number even to topics outside mathematics. Let w be a word over an alphabet ? and let Gw be the simple graph, whose vertices are elements of ? contained in w, in which two vertices are adjacent if and only if the corresponding symbols are consecutive in w. When w is a sequence of letters in a sentence of a natural language, or a sequence of words in a text, the crossing number of Gw was proposed as a measure of complexity of the language [63]. The difficulty of this graph invariant is probably the reason that not much research has been done in this direction. Thus eodermdromes, which are meaningful words or sentences w with nonplanar graphs Gw, have become a domain of recreative linguistics [29]. 2.6 Contribution of this thesis We extend three areas of the theory of the crossing number in this thesis: we investigate crossing-critical graphs, prove the exact crossing numbers of several Cartesian products, and introduce a minor-monotone variant of the crossing number. 26 Results on the crossing number In Chapter 3, we introduce a new graph operation, the zip product, which combines two graphs or two drawings. We establish a sufficient connectivity condition under which the zip product preserves the crossing numbers of graphs, as well as a symmetry condition under which it preserves their critical-ity. The theory of tiles by Pinontoan and Richter [96] is extended in Chapter 4 to yield a general construction of crossing-critical graphs. In Section 4.3.2, we develop the staircase strips, a new gadget used to establish the crossing numbers of certain graphs. We apply them together with the zip product in Chapter 5 to design three families of crossing-critical graphs and combine them into a seven-parameter family of crossing-critical graphs using which we prove the main result of the thesis: a careful choice of parameters allows us to prescribe not only any average degree r ? (3, 6), but also any sufficiently high crossing number. We thus settle Question 2.14 and combine the results ˇ of Salazar, Pinontoan and Richter with those of Sir´anˇ and Kochol. The aforementioned constructions extend our knowledge about the structure of crossing-critical graphs in two directions. First, the staircase strips show that there exist infinite families of almost cubic 3-connected k-crossing-critical graphs with relatively few vertices of degree four. According to Richter and Salazar, similar generalizations of Kochol’s 2-crossing-critical graphs were studied before, but their crossing numbers were not established until this thesis [101]. Second, Richter and Salazar observed that all known families of k-crossing-critical graphs with fixed k are built using tiles [100]. The zip product, with its ability to preserve criticality of graphs, demonstrates that the ring-like structure present in tiled k-crossing-critical graphs is not the only one: several crossing-critical graphs with such rings can be combined to yield a family of k-crossing-critical graphs, and each ring can grow independently to yield other graphs in the family. In Section 3.2, we show that criticality is contagious in the sense that performing a zip product of a crossing-critical and noncritical graph makes the edges involved in the product critical. Thus, we can turn noncritical graphs with a vertex cover satisfying a certain connectivity condition into a part of a crossing-critical graph using the zip product. Such structural consequences are discussed in Section 5.5. Cartesian products of graphs with trees can be built recursively using the zip product. However, when applying this operation to find the crossing numbers of such products, we are left with excessive vertices corresponding to the leaves of the tree. In some cases, we can successfully eliminate them and obtain exact crossing numbers. These cases include the Cartesian product of stars K1,n and wheels Wn with paths, as well as some other results of similar flavor. In particular, we prove Conjecture 2.10 for any n,m ? 1. We have mentioned that drawings of graphs with few crossings are of certain importance in VLSI design. Within the setup of the ordinary crossing 2.6 Contribution of this thesis 27 (a) (b) (c) Figure 2.1: mcr and the crossing numbers of electronic circuits. number, the goal is to minimize the number of crossings in the given graph of an electronic circuit. In this setup, we do not use the equality of the electric potential of the wires in the circuit that do not contain any electronic element. They can be contracted to a single vertex and expanded in a different manner to yield an equivalent circuit, whose graph may have smaller crossing number. We illustrate this in Figure 2.1: (a) shows the original drawing of a circuit of an ultrasonic transmitter [129], (b) shows the equivalent circuit in which all the points with the same potential are contracted to a single vertex, and (c) shows an equivalent circuit with one crossing less than (a). The minor crossing number invariant that we study in Chapters 7–10 overcomes this problem. With this invariant of a graph G we seek the minimum number of crossings over all drawings of graphs that can be obtained from G by replacing its vertices with arbitrary trees. In an electronic circuit such a replacement corresponds to spreading the wires with equal potential. Thus obtained, a realizing graph of G has G as a minor and this variant of the crossing number is minor-monotone. It therefore solves a problem, discussed by Seymour [7], who complained: “Isn’t it a shame that crossing numbers don’t work well with minors?” Indeed, a removal of an edge never increases the crossing number, but a contraction can change it in either way. Our studies of this new invariant focus on establishing lower bounds (Chapter 8), studying structure of graphs with bounded minor crossing numbers (Chapter 9), and on applying minor crossing number bounds to certain families of graphs (Chapter 10). Our first lower bound uses the maximum degree of a graph and establishes a sandwich theorem for the minor crossing number in terms of the ordinary crossing number. It generalizes a result of Moreno and Salazar, who proved a similar result for graphs of maximum degree four in [86]. We also bound the minor crossing number in terms of the genus of a graph and improve a bound implied by the Euler Formula by using the newly discovered structure of graphs with bounded minor crossing numbers. In addition 28 Results on the crossing number to several bounds for complete graphs, complete bipartite graphs, hypercubes, and Cartesian products of two cycles, we establish exact results for the minor crossing numbers of Kn, 1 ? n ? 8, and of K3,n and K4,n, n ? 3. Part II Crossing-critical Graphs 29 Chapter 3 Zip product In this section, we introduce the zip product, an operation on graphs and their drawings that under certain conditions preserves the crossing numbers and the criticality of graphs. We apply this operation in Chapter 5 and construct crossing-critical graphs with prescribed crossing number and average degree. Another application follows in Chapter 6, where we establish the crossing numbers of graphs of several families. 3.1 Definition and basic lemmas For % = 1, 2, let d be a graph and let Vi G V(Gi) be its vertex of degree d. Let Ni = N*G.(vi) be the multiplicity neighborhood of Vi and let a : A^ -»¦ N2 be a bijection. We call a a zip function of graphs Gx and G2 at vertices vx and v2. The zip product of graphs Gx and G2 according to a is defined to be the graph Gi Qa G2 obtained from the disjoint union of Gx - vx and G2 - v2 after adding the edge ua(u) for every u e Nx. Let Gx V1QV2 G2 denote the set of all graphs obtained as a zip product Gx Qa G2 for some bijection a : Nx -»¦ N2. Let Di be a drawing of the graph d and let a bijection m : Nt -»¦ {1,... ,d} be a labeling respecting the edge rotation around Vi in A. We define a : iVi -»¦ iV2, i and D2 at vertices Wl and v2. The zip product of Dx and L>2 according to a is the drawing L>i ©^ D2 obtained from Dx by adding a mirrored copy of D2 that has w2 incident with the infinite face disjointly into some face of Dx incident with v1, by removing vertices vx and v2 together with small disks around them from the drawings, and then by joining the edges according to function a, cf. Figure 3.1. As a respects the edge rotation around vx and v2, the edges between L>i and D2 may be drawn without introducing any new crossings. Clearly, L>i Qa D2 is a drawing of Gx Qa G2. This implies the following: 31 32 Zip product D1\\ \ Dx *:%r/-. 7Ti •- Ä ' 7V'2 d2 (/I y\ d'2 Figure 3.1: Zip product of drawings Dx and L>2. Lemma 3.1. For i = 1,2, let A be an optimal drawing of Gi, let Vi G V(Gi) be a vertex of degree d, and let a be a zip function of Dx and D2 at vx and v2. Then, cr(Gi ©CT G2) < cr(Gi) + cr(G2). Lemma 3.2. Let Gx and G2 be two graphs with vertices vx G V(GX) and v2 G V(G2) of degree d, and let G G GlviQV2 G2. Then, cr(G) < cr(Gi) + cr(G2) + (d~1). Proof. Let G = Gx &a G2. For i =1,2, let A be an optimal drawing of G*. The edge rotation vn around Wl in L>i combined with a induces a permutation 7T2 of edges incident with v2. From L>2, we can obtain a drawing L>2 respecting 7T2 by introducing at most f*"1) new crossings. The drawing D = DlQa D'2 of G has at most cr(Gi) + cr(G2) + (^~l) crossings. ? In specific cases, the number of crossings can be further minimized using the symmetry of involved graphs. Let v G V(G) be a vertex of degree d in G. A bundle of v is a set B of d edge disjoint paths from v to some vertex u G V(G), u=v. Vertex t; is the source of the bundle and u is its sink. Other vertices on the paths of B are internal vertices of the bundle. Let E(B) = E(B) n L(G - w) denote the set of edges of B that are not incident with v. They are called distant edges of B. Two bundles Bx and S2 of v are coherent if their sets of distant edges are disjoint. Edges of a bundle B that are not distant are near edges. Lemma 3.3. For % = 1,2, let G* be a graph, Vi G V(Gi), deg(^) = d, Nt = N*G.(vi). Assume that v2 has a bundle B in G2. For every bijection o : Nx -»¦ N2and every drawing D ofG = G1Q<7G2, there are at least cr(Gi) crossings in D of an edge from E(GX - vx) with an edge from E(GX - vx) U ˘ (B) U {ua(u)\ueNl}. Dl Qa D2 3.1 Definition and basic lemmas 33 P3 u Pi u n u n D D D' Figure 3.2: Splitting the internal vertices of a bundle. Proof. Let G be the subgraph of G induced by the edges of E(Gl - vx) U E(B) U {ua(u) | u G Nx} C P(G) and let D be the P-induced subdrawing of G. We establish the claim by splitting some vertices of D and producing a drawing D' of a subdivision of Gx. Let m G V (G) be the sink of P and w G V(G) an internal vertex of the bundle B. Assume that w lies on t paths Pi,..., Pt of B. We split w into t vertices wu...,wt, such that ^ is incident precisely with the two edges of P,-incident with w. The graph G obtained from G after performing this split on all internal vertices of B is isomorphic to a subdivision of Gx. From D, we produce a drawing ^ of G by removing a small disk around every internal vertex w of P in D and connecting the edges of paths through w in the interior of the disk (cf. Figure 3.2). We can eliminate possible new crossings by rerouting crossed pairs of paths and possibly relocating the vertices Wi inside the corresponding disks, as well as any crossing of two edges of E(B) U {ua(u) | u G N^, since the crossed paths emanate from the same vertex u. Let D' be the drawing of G obtained from D by such uncrossing. As D' is a drawing of a subdivision of d and all the crossings of D' appear in D, the claim follows. ? The process applied to the P-induced subdrawing of G in the proof of Lemma 3.3 is called splitting the internal vertices of the bundle P. Theorem 3.4. For % = 1,2, let G* be a graph, Vi G V(Gi) its vertex of degree d, and Nt = N*G.(vi). Also assume that Vi has two coherent bundles BiA and Bit2 in d. Then, cr(Gi Qa G2) > cr(Gi) + cr(G2) for any bijection o : Ni ->¦ N2. Proof. Let G = Gl&(7 G2 and F = {va(v) \v e Nx} C E(G). For i,j = 1,2, let Ei = E(Gi - v) C E(G) and let G^ be the subgraph of G spanned by the edges of Ei, F^ = E(Bi3) and P. 34 Zip product Let D be an optimal drawing of G, and let Aj be the induced subdrawing of Gij. Lemma 3.3 implies cr(d) < crD(El} Ex) + crD(El}F) + crD(E1,F2j), thus also cr(Gi) < crD(E1} Ex) + cr D(E1}F) + ± cr D(E1}F21 U F22). A similar inequality holds for cr(G2). The sum of the two inequalities yields: cr(Gi) + cr(G2) < crD(E1} Ex) + crD(L2, L2) + i (crD(JB1, F21 U F22) + crD(L2, Fn U F12)) + crD(LiUL2,F) < crD(Li, L1 U F) + crD(L2, L2UF) + crD(Li, L2) = cr(L>)-crD(F,F) < cr(G). Note that F„ C ^ are disjoint for i, j = 1, 2, thus a crossing of any ee^ with some f E E2 is counted at most twice in the sum of crD(Ei} F3_itj). This justifies the second inequality. ' ? If one of the graphs is planar, we need only one bundle. Lemma 3.5. For i = 1,2, let G* be a graph, Vi G V(Gi) its vertex of degree d, and Ni = N*G.(vi). Assume that Gx is planar and that vx has a bundle Bx in Gi. Then, cr(G1Q cr(G2) for any bijection a : Nt -»¦ N2. Equality holds if, for % = 1,2, a respects the edge rotation around Vi in some optimal drawing Di of d. Proof. Since vx has a bundle in Gl, any drawing of G = Gx &a G2 can be turned into a drawing of a subdivision of G2 by splitting the bundle B. The lower bound follows. If a respects the edge rotation around vx and v2, then the drawing D = DxQa D2 contains only the crossings of D2 and the claim follows. ? We use the following observations in iterative applications of the zip product. Lemma 3.6. Let Gx and G2 be disjoint graphs, Vi G V(Gi), degG.(^) = d, andGeGlviQV2G2. (i) Ifv2 has a bundle in G2 and v G V(Gi) has k pairwise coherent bundles in Gi, then v has k pairwise coherent bundles in G. (ii) If, fori = 1,2, the graph G; is ^-connected, h > 2, then G is k-connected for fc = min(fci,fc2). (iii) If, for i = 1,2, the graph G* is h-edge-connected, h > 2, then G is k-edge-connected for k = min(kl}k2). 3.2 Homogeneity condition 35 Proof. (i): Assume G = d Qa G2 and let Bu ..., Bk be the bundles of v in d and B the bundle of v2 in G2. For an edge e = uv2, let Pe be the path of B containing e. A path P G (jjLi #* can have at most two edges that are in P incident with vx. If there are none, define P' = P. If there is only one such edge wv1, define P' = Pwa(w)Pe, e = a(w)v2. For two such edges wvx = zvx on P, define P' = Pwa(w)PePfa(z)zP, e = a(w)v2, f = a(z)v2. As the paths of B are pairwise edge disjoint and each of them is used at most once in the construction of some P', the paths P{ and P'2 are edge disjoint for edge disjoint paths P1}P2E Uti Bi. If pi> p2 in G: share only the edge incident with v, so do P[ and P^ in G. If u = ^ is the endvertex of the path P G Uti 5*, then m is the endvertex of P'. If vx is the endvertex of the path P G Uti Bi, then the endvertex of P' is the sink of B. These three statements imply that the sets B'i = {P' | P G Pi}, i = 1,..., k, are pairwise coherent bundles of t; in G. (ii): Let 5 C V(G) be a separator of G. If 5 C d-Vi, then, as Ga-i-^-i is nonempty and (k3-i - 1)-connected, S is a separator in G, and |5| > fc. Let $ = 5 n d - Vi and ^ = 0 for i = 1, 2. If S* U Vi is a separator in d for one of i = 1, 2, then |S| > k. Otherwise, the vertices of d - Vi - S are all in the same component of G - S for both i = 1,2, thus \S\ > d > k. (iii): The argument is similar to (ii). ? 3.2 Homogeneity condition In this section, we introduce a sufficient condition for the zip product to preserve criticality of graphs. Let S C V (G) be a set and ? C Aut(G) a group. We say that S is ?-homogeneous in G if any permutation vr of S can be extended to an automorphism a G ?. For S C F(G), let ?(S) be the pointwise stabilizer of S in Aut(G). We say that a vertex v G V(G) has a homogeneous neighborhood in G if NG(v) is ?({w})-homogeneous in G. If all the vertices in NG(v) have the same set of neighbors for a vertex v G V(G), then t; has a homogeneous neighborhood G. Thus, every vertex of a complete or complete bipartite graph K has a homogeneous neighborhood in if. A vertex w in a graph G is semiactive if it has two coherent bundles in G. If, in addition, t; has no incident multiple edges and has a homogeneous neighborhood, then v is active. S(G) and A(G) respectively denote the sets of semiactive and active vertices of G. Theorem 3.7. For i = 1,2, let Gi be a graph with a vertex Vi G V(d) of degree d. If vx G S(d) and v2 G A(G2), then the following holds for every 36 Zip product graphGeGlviGV2G2: (i) cr(G) = cr(G1) + cr(G2). If, in addition, vx G A(GX), then: (ii) If, for % = 1,2, the graph G* is h-crossing-critical, then G is k-crossing-critical for k = max {cr(Gt) + fc3-* M G {1, 2}}. (iii) If, for j G {1,2}, v G A(G3), v ^ v3, and NGj(v) is TGj({v,v3})- {1,2}, v G A{Gj), homogeneous, then v G A(G). Proof. For the proof, assume Nx = NGi(Vl), N2 = NG2(v2), and let the zip function of G be a : Nt -»¦ iV2. (i): For i = 1,2, let A be an optimal drawing of G; and let m denote the vertex rotation around Vi in A- Because there exists an automorphism p G rG2({w2}) with p/N2 = ama-1^1, we can rearrange the vertices in D2 using p and obtain a drawing D'2 of G2 with cr(L>2) crossings in which the vertex rotation of v2 is avna"1. Since w2 has no multiple edges, Claim (i) follows by Lemma 3.1 and Theorem 3.4. (ii): Claim (i) implies cr(G) > k. Let e G E{G), and assume e G L(Gi -vi). Let Dx be an optimal drawing of Gx - e and D2 an optimal drawing of G2. We adjust L>2 using the appropriate automorphism in TG2({v2}) similarly as in the proof of (i) and combine D2 with Dx to produce a drawing of G with at most k crossings. Similar arguments apply for e G E(G2 - v2). If e = w(t;) for v e Nu let L>i be an optimal drawing of Gx - vvx and D2 an optimal drawing of G2 - v2a(v). Let vn be the vertex rotation around vx in L>i and p G rG2({w2}) an automorphism of G2 with p/(N2\{a(v)}) = aW1. The vertices of N2 can be rearranged with p as in the proof of (i), thus by Lemma 3.1, G - e can be drawn with at most h + k2 crossings. (iii): Assume that j = 1, case j = 2 is similar. Due to d 6 5(d), Lemma 3.6 (i) implies v G S(G). For a permutation vr of iV = NG.{v), there exists a! G rGl({w,Wl}), such that has at most cr(G) + kj + Ei^- cr(Gi) < k crossings. Case 2: Assume e ^ ^(Gi - v) for any i G {1,... ,L}. As 5 is a vertex cover in G, there exists j G {1,...,t}, such that — e connects some neighbor x of M, G y(Gj) with some neighbor y of v j in G,-. Let d = vjV G ^(G,), e2 = UjX G ^(G,), and let Dx be an optimal drawing of G j - el with v j on the infinite face and D2 an optimal drawing of G j - e2 with Uj in the infinite face. We can combine Dx - Vj and D2 - Uj into a drawing D of G - e. By Theorem 3.8 (i), L> has at most cr(G - e) + kj + Y,i+j cr(Gi) < fc crossings. ? 38 Zip product Figure 3.3: Graph with a vertex cover of cubic vertices each having two coherent bundles. Having a vertex cover consisting of cubic vertices with two coherent bundles seems a strong condition and one may think it forces the graph to be crossing-critical. This, however, is not the case: the white vertices of the graph G in Figure 3.3 form such a vertex cover, but since cr(G) = 1 and not all the edges lie in the K3,3 subdivision in G, this graph is not crossing-critical. Lean~os and Salazar established a decomposition of 2-connected crossing-critical graphs into smaller 3-connected crossing-critical graphs in Theorem 2.17. Theorem 3.9, in combination with Figure 3.3, suggests that a similar decomposition does not exist for 3-connected crossing-critical graphs. Chapter 4 Tiles In this chapter, we present a variant of the theory of tiles developed by Pinon-toan and Richter [96]. In particular, we consider general sequences of not necessarily equal tiles, avoid the condition that the tiles be connected, and allow forming double edges when joining tiles. Such generalizations do not hinder the arguments of [96] and are useful in further investigations of tiled graphs. We establish an effective bound on the number of tiles needed to imply lower bounds on crossing numbers. Finally, we combine these improvements into a general construction of crossing-critical graphs. 4.1 Definition and basic lemmas Let G be a graph and A = (A0,...,Aj), P = (po,---,Pr) two sequences of distinct vertices, such that no vertex of G appears in both. The triple T = (G, A, p) is called a tile. To simplify the notation, we may sometimes use T in place of its graph G and we may consider sequences A and p as sets of vertices. For u, v E A or u, v E p, we use u < v or u > v whenever u precedes or succeeds v in the respective sequence. A drawing of G in the unit square [0,1] x [0,1] that meets the boundary of the square precisely in the vertices of the left wall A, all drawn in {0} x [0,1], and the right wall p, all drawn in {1} x [0,1], is a tile drawing of T if the sequence of decreasing y-coordinates of the vertices of each A and p respects the corresponding sequence A or p. The tile crossing number tcr(T) of a tile T is the minimum crossing number over all tile drawings of T. Let T = (G, A, p) and T' = (G', A', p') be two tiles. We say that T is compatible with V if \p\ = |A'|. A tile T is cyclically-compatible if it is compatible with itself. A sequence of tiles T = (T0,..., Tm) is compatible if T* is compatible with Ti+1 for % = 0,..., m - 1. It is cyclically-compatible if it is 39 40 Tiles compatible and Tm is compatible with T0. All sequences of tiles are assumed to be compatible. The join of two compatible tiles T and V is defined as T ® V = (G ® G', A, p'), where G ® G' is the graph obtained from the disjoint union of G and G' by identifying Pi with A^ for % = 0,..., \p\ - 1. This operation is associative, thus we can define the join of a compatible sequence of tiles T = (T0,..., Tm) to be the tile ®T = T0 ® 7\ ® ... ® Tm. Note that we may produce multiple edges or vertices of degree two when joining tiles. We keep the double edges, but remove the vertices of degree two by contracting one of the incident edges. For a cyclically-compatible tile T = (G, A, p), we define its cyclization oT as the graph, obtained from G by identifying A* with Pi for % = 0,..., \p\ - 1. Similarly, we define the cyclization of a cyclically-compatible sequence of tiles asoT = o(®T). The suspension of a tile T = (G, A, p) is the graph T*, which is obtained from T by adding a new vertex v (called the apex of T*) to G and connecting it precisely to all the vertices of A U p. Note that neither the cyclization nor the suspension of a tile is a tile. Lemma 4.1 ([96]). Let T be a tile. Then, cr(T*) < tcr(T). Let T be a cyclically-compatible tile. Then, cr(oT) < tcr(T). Let T = (T0,... ,Tm) be a compatible sequence of tiles. Then, tcr(®T) < ZotcT(Ti). For a sequence u, let Ü denote the reversed sequence. For a tile T = (G, A, p), let its right-inverted tile T* be the tile (G, A,p), its left-inverted tile IT be the tile (G, X,p), and its inverted tile be the tile IT* = (G, X,p). The reversed tile of T is the tile T" = (G, p, A). Let T = (T0,... ,Tm) be a sequence of tiles. A reversed sequence of T is the sequence T" = (T^,... ,T0"). A twist of T is the sequence T* = (T0,..., Tm_i, Ti). Let i = 0,..., m. Then, an i-flip of T is the sequence T* = (To,...,^.!,^, lTi+1)Ti+2)...,Tm), an z-cut of T is the sequence T/i = (Ti+1,... ,Tm,T0,... ,Tt_i), and an i-shift of T is the sequence % = (Ti}..., Tm, T0,..., Ti+l). For the last two operations, cyclic compatibility of T is required. Two sequences of tiles T and V of the same length m are equivalent if one can be obtained from the other by a sequence of shifts, flips, and reversals. It is easy to see that the graphs oT and oT' are equal for equivalent cyclically-compatible sequences T and T and thus have the same crossing number. 4.2 Properties of tiles 41 4.2 Properties of tiles We say that a tile T = (G, A, p) is planar if tcr(T) = 0 holds. It is connected if G is connected. It is perfect if: (p.i) |A| = |p|, (p.ii) both graphs G - A and G - p are connected, (p.iii) for every v G A or v G p there is a path from w to a vertex in p (A) in G internally disjoint from A (p), and (p.iv) for every 0 < % < j < |A| there is a pair of disjoint paths P^ and P^ in G, such that Ptj joins A* with p; and Pjt joins A,- with Pj. Note that perfect tiles are connected. Lemma 4.2 ([96]). For a cyclically-compatible perfect planar tile T and a compatible sequence T = (T0,... ,Tm,T), there exists n G N, such that for every k > n, tcr((®T) ® (Tfc)) = tcr((®T) ® (Tn)). Let T = (G, A, p) be a tile and H a graph that contains G as a subgraph. The complement of the tile T in H is the tile H-T= (H[(V(H)\V(G))U\U p] - E(G),p, A). We can consider it as the edge complement of the subgraph G of H from which we remove all the vertices of T not in its walls. Whenever o(T ®(H- T)) = H, i.e. if the vertices of A U p separate G from H-G,we say that T is a tile in H. Using this concept, the following lemma shows the essence of perfect tiles. Lemma 4.3. Let T = (G, A, p) be a perfect planar tile in a graph H, such that there exist two disjoint connected subgraphs GA and Gp of H contained in the same component ofH-T and with G D GA = (A, 0), G n Gp = (p, 0). If E{G) and either E(GX) or E{GP) are not crossed in some drawing D of H, then the D-induced drawings of T and its complement H - T are homeomorphic to tile drawings. Proof. There is only one component ofH-T containing the vertices of A U p, and as the edges of other components do not cross G nor influence its induced drawing, we may assume that H - T is that component and, in particular, it is connected. Denote by DT the ^-induced drawing of T, by T- the tile H - T, and by D- the ^-induced drawing of T-. As the edges of T are not crossed in D and T- is connected, there is a face F of DT containing D-. The boundary of F contains all vertices of T n T- = A U p. Let W be the facial walk of F. 42 Tiles No vertex of A U p appears twice in W: such a vertex would be a cutvertex in the planar graph G. Then either G - A or G - p would not be connected, violating (p.ii), or some vertex in A U p would have no path to the opposite wall satisfying (p.iii). Let W be the induced sequence of vertices of A U p in W. As the edges of Gx or Gp are not crossed in D and T, Gx, and Gp are connected, the vertices of A do not interlace with the vertices of pinW. The ordering of A in W is the inverse ordering of pinW, since the disjoint paths from (p.iv) do not cross in DT. The planarity and the connectedness of T imply that whenever i < j < I or i > j > I, there is a path Q from Pß_to A* disjoint from Py. Q does not cross Ptj in DT, thus W = Xp or W = pX. The claim follows. ? The above arguments were in [96] combined with Lemma 4.2 to demonstrate the following: Theorem 4.4 ([96]). Let T be a perfect planar tile and for k> 1 let Tk_= Tfc 0 Tl 0 Tk. Then there exist integers n, N, such that cr(o(ffc)) = tcr(fra) for every k> N. We establish effective values of n and iV from the above theorem: Theorem 4.5. Let T = (T0,... ,Th ... ,Tm) be a cyclically-compatible sequence of tiles. Assume that for some integer k > 0 the following hold: m > ik-2, tcr(0T/i) > k, and the tile % is a perfect planar tile, both for every % = 0,... ,m, % ^ /. Then, cr(oT) > k. Proof. We may assume k > 1. Let G = oT and let D be an optimal drawing of G. Assume that D has less than k crossings. Then there are at most 2k - 1 tiles in the set S = {Ti | % = I or E{Ti) crossed in D}. The circular sequence T is by the tiles of S fragmented into at most 2k - 1 segments. By the pigeonhole principle the set T\S, which consists of at least 2k tiles, contains two consecutive tiles T{Ti+l. Assume for simplicity that i=l, then either T0 or T3 is distinct from Th Lemma 4.3 with (G,T1}T0,T2) or (G,T2,T1}T3) in place of (H,T, Gx, Gp) establishes that the induced drawing D~ of G - Tj is a tile drawing for some j E {1,2}. Since D~ contains all the crossings of D, this contradicts tcr(0(T/j)) > k, and the claim follows. ? Corollary 4.6. Let T = (T0,... ,7],... ,Tm) be a cyclically-compatible sequence of tiles and k = min^tcr(0T/i). If m > ik - 2 and the tile Tt is a perfect planar tile for every % = 0,... , m, % ^ /, then cr(oT) = k. 4.3 Gadgets in tiles 43 Proof. By Lemma 4.1 and the planarity of tiles, cr(oT) < tcr((®T/z) ®T;) < %) for any % ^ /, thus cr(oT) < k. Theorem 4.5 establishes k as a lower bound and the claim follows. ? tcr(®T A tile T is k-degenerate if it is perfect, planar, and tcr(Tl - e) < k for any edge e G E{T). A sequence of tiles T = (T0,... ,Tm) is k-critical if the tile Ti is fc-degenerate for every i = 0,... ,m and min^mtcr(®(Tl/«)) > k. Note that tcr(Tl) > k for every tile T in a fc-critical sequence. Corollary 4.7. Let T = (T0,..., Tm) be a k-critical sequence of tiles. Then, T = ®T is a k-degenerate tile. If m > 4 then o(Tl) is a k-crossing-critical graph. T = ®T is a k-degenerate tile. If m > 4k - 2 and T is cyclically-compatible, Proof. Lemma 4.1 implies that T is a planar tile. By induction it is easy to show that T is a perfect tile. Let e be an edge of T and let i be such that e G Ti. The sequence V = (T0,..., T^, t} , lTi+ll,..., *tI) is equivalent to Tl. Lemma 4.1 establishes tcr(Tl - e) = tcr((®T/) - e) < tcr(7f - e) < k, thus T is a fc-degenerate tile. Let T be cyclically-compatible. Then cr((oTl) - e) < k for any edge e G E{T). Theorem 4.5 implies cr(o(Tl)) > k for m > 4k - 2. Thus, o(Tl) is a fc-crossing-critical graph. D 4.3 Gadgets in tiles Results of Section 4.2 provide sufficient conditions for the crossing numbers of certain graphs to be estimated in terms of the tile crossing numbers of their subgraphs. This section develops some techniques to estimate the tile crossing number. A general tool we employ for this purpose is the concept of a gadget. We do not define it formally; a gadget can be any structure inside a tile T = (G, A, p), which guarantees a certain number of crossings in every tile drawing of T. Four specific types of gadgets are presented: twisted pairs, staircase strips, cloned vertices, and wheel gadgets. We supplement them by related results that point out the principles using which new gadgets could be defined. In general, there can be many gadgets inside a single tile. Whenever they are edge disjoint, the crossings they force in tile drawings are distinct. The following weakening of disjointness enables us to prove stronger results. For clarity we first state the condition in its set-theoretic form. Let A1}B1} A2, B2 be four sets. The unordered pairs {A^Bt} and {A2, B2} are coherent if one of the sets Xi} X G {A,B}, % G {1,2}, is disjoint from A3t U B3t. 44 Tiles Lemma 4.8. Let {A, B} and {A', B'} be two pairs of sets. If they are coherent and aeA,beB,a'eA'andb'eB', (4.1) then the unordered pairs {a,b} and {a',b'} are distinct. Conversely, if (4.1) ,&}, {a',b' pairs {A,B}, {A',B'} are coherent. implies distinctness of {a,b}, {a',b'} for every quadruple a,b,a',b', then the Proof. Suppose the pairs are not distinct, then either a = a' and b = b', or a = b' and b = a'. In both cases, every set has a member in the union of the other pair, and the pairs are not coherent. For the converse, suppose the pairs would not be coherent. Then every set would contain an element in the union of the opposite pair. Let x E A D A', assuming the intersection is not empty. If there is an element y E B' D B, then the quadruple a = x, b = y, a' = x, b' = y satisfies (4.1) but does not form two distinct pairs. If B n B' is empty, then there must be a' E B D A' and b' EB'n A. The quadruple a = a', b = b', a', b' satisfies (4.1). Assuming xEAr\B',a similar analysis applies and the claim follows. ? Lemma 4.8 has an immediate application to crossings: whenever the pairs of edges {ex, fx} and {ey, fy} are distinct for two crossings x and y, the crossings x and y are distinct. Distinctness of crossings induced by two coherent pairs of sets of edges in a graph follows. The notion of coherence can be generalized. Let {Au ..., Am} and {Bu ..., Bn} be two families of sets. They are coherent if the two pairs {A,Aj} and {Bk, Bi} are coherent for every 0 < i < j < m, 0 < k < I < n. 4.3.1 Twisted pairs A path P in G is a traversing path in a tile T = (G, A, p) if there exist indices i(P) E {0,..., |A| - 1} and j(P) E {0,... , \p\ - 1} such that P is a path from A(P) = Ai(P) to p(P) = pj{P) and A(P), p(P) are the only wall vertices that lie on P. An (unordered) pair of disjoint traversing paths {P, Q} is aligned if i(P) < i(Q) is equivalent to j(P) < j(Q), and twisted otherwise. Disjointness of the traversing paths in a twisted pair {P, Q} implies that some edge of P must cross some edge of Q in any tile drawing of T. Two pairs {P, Q} and {P7, Q'} of traversing paths in T are coherent if {E(P),E(Q)} and {E(P'),E(Q')} are coherent. A family of pairwise coherent twisted (respectively, aligned) pairs of traversing paths in a tile T is called a twisted (aligned) family in T. Lemma 4.9 ([96]). Let T be a twisted family in a tile T. Then,tcr(T) > \F\. 4.3 Gadgets in tiles 45 Let a tile T be compatible with V and let {P, Q} be a twisted pair of traversing paths of T. An aligned pair {P', Q'} of traversing paths in V extends {P, Q} to the right if j(P) = i(P'), j(Q) = i(Q'). Then {PP', QQ'} is T' an aligned family :F' in T', for which there exists a bijection e : T ^ T', such that the pair e({P, Q}) E T' extends the pair {P, Q} on the right. In this case, the family T®eT' = {{PP', QQ'} | {P', Q'} = e{{P, Q})} is a twisted family in T 0 T'. Extending to the left is defined similarly. Let T = (T0,..., Th ..., Tm) be a compatible sequence of tiles and Tx a twisted family in 7j. If, for % = I + 1,..., m (respectively, i = I - 1,..., 0), there exist aligned right- (left-) extending families Ti of Ji0.. .0^-1 (^+i0.. -0^-i), then Ti propagates to the right (left) in T. J=i propagates in cyclically-compatible T if it propagates both to the left and to the right in every cut T/i, % = 0,..., m, % ^ /. A twisted family T in a tile T saturates T if tcr(T) = \T\, i.e. there exists a tile drawing of T with |F| crossings. Clearly, all these crossings must be on the edges of pairs of paths in 3=. Corollary 4.10. Let T = (T0,... ,7],... , Tm) be a cyclically-compatible sequence of tiles and T a twisted family in Tt that propagates in T. If m > 4|F| - 2 and the tile Ti is a perfect planar tile for every % = 0,..., m, % ^ /, then cr(oT) > \F\. If T saturates T, then the equality holds. Proof. As T propagates in T, Lemma 4.9 implies min^tcr(0(T/i)) > \T\. Theorem 4.5 establishes the claim. D 4.3.2 Staircase strips In this section, we study twisted staircase strips. Using these gadgets, we later construct new crossing-critical graphs with average degree close to three. Let V = {Pi,P2,..., Pn} be a sequence of traversing paths in a tile T with the property A(Pt) < \(P3) and p(Pt) > p(P3) for % < j. Assume that they are pairwise disjoint, except for the pairs Pl} P2 and Pra_i, Pn which may share vertices, but not edges. For u E V(Pi) n V(P2) and v E V(P„_i) n V(Pn), we say that u is left of v if there exist internally disjoint paths Qu and Qv from u to v such that (cf. Figure 4.1): (s.i) there exist vertices u^u'^ ... ,un,u'n that appear in this order on Qu, (s.ii) there exist vertices Vl,v[,...,vn,v'n that appear in this order on Qv, (s.iii) u = U\ = u[ = u2 = V\ and v = u'n = v'n_1 = vn = v'n, 46 Tiles U = U\ = u\ = U2 = V\ Us = u'3 u'2 v[ v2 S2 s' s" ^: 3 un V = u'n = V,n_l = Vn = v'n «5 u'5 Vn-1 Figure 4.1: A general staircase strip in a tile. Leftmost and rightmost arrows indicate the ordering of the wall vertices. Dashed edges are part of the tile but not of the staircase strip. e (s.iv) v[,v2,v2,u2 ^ Pi n P2 and vn-Uun.h<_1;un k) - 1. Proof. If a wall vertex v in a tile T has degree d, then the tile crossing number of T is not changed if d new neighbors v1}... ,vd of degree one are attached to v and v is in its wall replaced byvu...,vd. Thus, we may assume that all paths in V have distinct startvertices in A and distinct endvertices in p. Let D be any optimal tile drawing of T. By Lemma 4.9 there are at least g) - 2 crossings in D, since the set T = {{P, Pj} | 1 < i < j < n} \ {{Pi, P2}, {Pn-i, Pn}} is a twisted family in T. For {Pi} Pj} e T, let Pt cross Pj at Xij. In what follows, we contradict the assumption xiyj are all the crossings ofD. (4.2) For i = 1,..., ra, let P* be oriented from A(P*) to p(Pi). The assumption (4.2) implies that the induced drawing of every P* is a simple curve. This curve splits the unit square A = I x I containing D into two disjoint open disks, the lower disk A" bordering [0,1] x {0} and the upper disk A+ bordering [0,1] x {1}. Claim 1: At xi>j, the path P,- crosses from A" into A+ and the path Pi crosses from A+ into A". This follows from % < j and the orientation of paths Pi and Pj. As A(P2) G A^ and p(P2) G A+, there is a vertex u G V(Pi) n V(P2) where P2 crosses Pi from A^ to A+ Also, there is a vertex v G F(P„_i) n V(Pn), such that Pra_i crosses from A+ into A" at v. Then Claim 1 holds for x1>2 = u and xn_i,n = v. By symmetry, we may assume that u is left of v in T. Let Qu and Qv be the corresponding paths in T. P2 enters A+ at u, and (4.2), (s.iii), (s.iv), and (s.v) imply u'2 G A+ Similarly, vn_x G A+ by (4.2), (s.iv), (s.iii), and (s.vi). Claim 2: If any point y of w\Qw lies in A" for w G {u,v} and % G {l,...,n},Wi^ Un-i, then the path Qw must at w[ enter A". II w ^ u or % ^ n - 1, the segment w[Qwy does not cross from A+ to A" due to Claim 1, thus it must lie in Aj\ Claim 3: If there is a point y of QwWi in A" for w G {u, v} and % G {1, ...,n},Wi= v2, then Qw must at Wi leave A". Otherwise, the segment yQwWi would contradict Claim 1 at Xji for some j < %. 48 Tiles Claim 4: For 3 < i < n, neither of ui)Vi lies in ?^. Assume some Ui G ?i. As u'2 G ?+, the path Qu would contradict Claim 1 at xltj for some j, 1 < j < i. Assume vt e ?j. Due to the orientation of Pi, (4.2),' and (s.x), ntG?[, a contradiction. Claim 5: For 1 < % < n - 2, neither ofv!i}v[ lies in ?". Assume v[ G ?". As vn.x G ?+, the path Qv would contradict Claim 1 at xj>n for some j, Kj 2. Thus, Vi G A^ contradicts Claim 4. (3) z = zi)3 = xhn implies un G A~[. (4) z = z2,i = xi}2 for some i > 2, then ti; G A[. (5) z = z2)2 = Xij is a crossing of Si and Rj. Claim 6 implies that 1 < % < j < n. Choose smallest such 1 and then smallest j. Qv starts in A" and since z is the first crossing of Qv with 7M (or one of the other eight cases would apply), Qv leaves A" and enters A+ at z. As the orientation of ia is aligned with the orientation of Rj} Si leaves A", which contradicts Claim 1. (6) z = z2)3 = xi>n for some % < n, then ^ G A", which contradicts Claim 5. (7) z = z3)i = x2,n-i implies v'2 G A~. 50 Tiles (8) z = z3,2 = Xi,n-i is the crossing of Pra_i and Sh then v[ G A". (9) z = z3)3 = v is a touching of 7M and 7". Thus, 7M and 7^ must cross at a new crossing and the statement of the theorem follows. D 4.3.3 Cloned vertices Cloned vertices were used as gadgets in the construction of 3-connected k-crossing-critical graphs by Kochol [72]. A clone of a vertex v in a graph G is a vertex v', such that N^(v) \ {v'} = Nh(v') \ M, i-e- v' has the same multiplicity neighborhood as v (modulo v, v'). A pair of clones (v,v') forms a clone gadget of degree din a graph G if no multiple edges are incident with these two vertices, |iVG(t;) \ {v'}\ = d and there exists a bundle B of v in the graph G - v'. For a vertex v and its clone v', let E(v,v') denote the set of edges emanating from v not incident with v'. We define E(v',v) similarly. Two clone gadgets (v^v'J, (t;2,tL) with respective bundles Bu B2 are coherent if the sets {E(v1} v[), E(v[, Vl), E^)} and {E(v2,v'2),E(v'2,v2),E(B2)} are coherent. Lemma 4.12. Let G be a graph, (v,v') a clone gadget of degree d in G, B a bundle of(v,v'), and D a drawing ofG. There are at least cr{K3,d) crossings in D involving two edges from distinct sets among E(v,v'), E(v',v), E(B). Proof. The argument uses the splitting of the bundle. Let G be the subgraph of G, induced by the edges of E(v, v') U E(v', v) U E(B), and let D be its ^-induced subdrawing. By splitting B in D (cf. Lemma 3.3), we obtain a drawing D' of a subdivision of K3>d. Since all the crossings of D' are the crossings of D, the claim follows. ' ? Proposition 4.13. Let {(v1} v[),..., (vt, v't)} be pairwise coherent clone gadgets in a graph G. Then, cr(G) > L*=1 cr(K3A), where & is the degree of the gadget (viX)- Proof. For some j G {1,..., t}, let {vhv'j) be a clone gadget of degree d j and Bj its bundle. By Lemma 4.12, there are at least cr{K3td.) crossings with the property that the two crossed edges come from two distinct sets among E(Bj), EivjXj), and Eiv'^Vj). As the clone gadgets {vi,vß, 1 < i < t, are pairwise coherent, these crossings can be exclusively attributed to the gadget {v^vfi. The claim follows. D 4.3 Gadgets in tiles 51 By generalizing bundles in graphs to bundles in tiles using suspensions of tiles, one can obtain more general clone gadgets that use the structure of tiles. We can also extend clone gadgets to graphs Kc>d for c> 3. 4.3.4 Wheel gadgets Cloned vertices use the minimal nonplanar graph X3)3 and its generalizations as the underlying structure to count crossings. In this section, we introduce the wheel gadgets that use the other minimal nonplanar graph, K5. To our knowledge, wheel gadgets were not applied to compute tile crossing numbers. We use them in Chapter 6 to study the crossing numbers of Cartesian products of wheels and trees. Let a vertex v have a bundle B of degree d with the sink m in a graph G. If there exists a cycle G in G, such that G intersects each path of B at most in one internal vertex of B, then the triple (v, B, G) forms a wheel in G. Cycle C is the rim of the wheel, vertex v is the inner hub, and u is the outer hub. An inner spoke is a subpath from v to C of some path in B, an outer spoke is a subpath from m to C of some path in B, and an axis is a path in B that has no vertices in common with C. A wheel gadget in G is a wheel in G that has at least one axis and at least three inner spokes that meet G in distinct vertices. Lemma 4.14. Let G be a simple graph, W = (v, B, C) a wheel gadget in G, and D a drawing ofG. Then, D contains (i) a crossing of some axis ofW with the rim, (ii) a crossing of some spoke ofW with the rim, or (iii) a crossing of an inner spoke with an outer spoke ofW. Proof. Let Pi,P2,^3 G B be three paths containing three inner spokes of W and Q E B an axis of W. Let D be the subdrawing of D induced by G U Q U (Jti pi and let D' be the drawing obtained from D by splitting the sub-bundle B' = {Pi,P2, P3}. The splitting preserves the crossings of its paths that occurred in the original drawing. Since the vertices of CC\B' lie on distinct paths of B', they are not split. D' is a drawing of a subdivision of K5, in which G corresponds to a triangle. We partition the edges of D' into four sets: the edges of the rim, the inner spokes, the outer spokes, and the axis. Any two curves in D' that represent edges from the same of these sets, share an endvertex of K5 and may be uncrossed in D'. The crossings between an axis and a spoke can also be uncrossed. Thus, some crossing of D' (originating in D) must be between edges from two different sets and not a crossing of an axis and a spoke, implying one of (i), (ii),or (iii). D 52 Tiles (a) (b) (c) (d) (e) (f) Figure 4.2: (a) Bridge. (b) Twisted pair. (c) Split pair. (d) Intertwined pair. (e) One-sided tripod. (f) Two-sided tripod. We can generalize wheel gadgets from graphs to tiles using generalized bundles similarly as clone gadgets. 4.3.5 Other gadgets In Sections 4.3.1–4.3.4, we have described several gadgets that were used in design of twisted crossing-critical graphs. These are graphs that are obtained from a twist of a cyclically-compatible sequence of perfect planar tiles. The crossed k-fences, a family of k-crossing-critical graphs designed by Hlinˇeny´ in [53], do not fit this pattern. However, the crossed k-fences can be described in terms of tiles and a possible gadget that establishes the lower bound on the tile crossing number is the bridge gadget presented in Figure 4.2 (a). This gadget has at least two crossings on its edges. It is not clear whether bridges in combination with twisted pairs suffice to establish the crossing numbers of crossed k-fences; perhaps we need a more involved gadget resembling staircase strips. Minimal gadgets in a tile T that force tcr(T) ? 1 have been classified by Mohar [83]. They are presented in Figure 4.2. Besides twisted pairs from Section 4.3.1 they include split pairs, intertwined pairs, and one- or two-sided tripods. All of these come in their left or right variants. In addition, paper [83] 4.3 Gadgets in tiles 53 classifies gadgets forcing tcr(T) > 1 in cylinder drawings of tiles (where vertices from the same wall of T are restricted to be drawn in the respective sequence in one component of the boundary of the cylinder). Note that some edges incident with wall vertices of bridges and tripods may be contracted. The new structure would still be a gadget of the same tile crossing number. Also, tripods are a generalized clone-gadgets, with the bundle of the two clones contained in the suspension T* and not in T. The zip product could be extended to tiles using generalized bundles. Applying the resulting operation to a vertex v of a tile T and a vertex m of a graph G, which both have two (generalized) coherent bundles, would result in a new tile V G TVQUG, whose tile crossing number would be at least the sum of tcr(T) and cr(G). Thus, any graph with positive crossing number and semiactive vertices can be used as a gadget. 54 Tiles Chapter 5 Constructions In this chapter, we apply results of Chapters 3 and 4 and construct four new families of critical graphs. Staircase strips are applied in design of a three-parameter family of crossing-critical graphs with average degree arbitrarily close to three. Using twisted pairs, we define two-parameter crossing-critical graphs with average degree arbitrarily close to six. An iterated zip product of graphs Kd,d' yields crossing-critical graphs with arbitrarily many vertices of degree d. We combine these graphs using the zip product and fine-tune their parameters to obtain crossing-critical graphs with prescribed average degree and crossing number. 5.1 Graphs with average degree close to three The reader shall have no difficulty rigorously describing the tile Sn, n > 3, an example of which is for n = 7 presented in Figure 5.1 (a). A staircase tile of width n > 3 is a tile obtained from Sn by contracting some (possibly zero) thick edges of Sn. Such a tile is a perfect planar tile. A staircase sequence of width n is a sequence of tiles of odd length in which staircase tiles of width n alternate with inverted staircase tiles of width n. Any staircase sequence is a cyclically-compatible sequence of tiles. Proposition 5.1. Let T be a staircase sequence of width n and odd length m > 4 g) - 5. The graph G = o(T l ) is a crossing-critical graph with cr(G) = G) -1. Proof. A generalization of the drawing in Figure 5.1 demonstrates that tcr(Sra) = g) -1. As m is odd, the cut T^/i contains a twisted staircase strip of width n for any i = 0,..., m-1, and Theorem 4.11 implies tcr(T ^ /i) > g) -1. 55 56 Constructions t *—•-------------*—» *~'-------------*T --------*—»----------------i 1 (a) (b) Figure 5.1: (a) The tile SV. (b) A tile drawing of S7 with 20 crossings. Planarity of tiles Sn and Lemma 4.1 establish equality and Corollary 4.6 implies cr(G) = g) - 1. After removing any edge from Sn, we can decrease the number of crossings in the drawing in Figure 5.1 (b). Thus, Sn is a g - 1-degenerate tile and r is a (g - 1-critical sequence; the criticality of G follows by Corollary 4.7. Let S; be the inverted tile Sn. For odd m > 1, let m be the staircase sequence (L„, S'n, Sn, S'n,..., Sn) of odd length m. Let S(n, m, c) denote the set of graphs, obtained from o(sl,m) by contracting c thick edges in the tiles of Sn>m. The graphs in S(n, m, c) are (g) - 1)-crossing-critical for m > 4g) - 5 and 0 < c < 2m(n - 2), by Proposition 5.1. They almost settle Question 2.14 for rational r G (3,4): Proposition 5.2. Let r = 3 + f with 1 < a < 6. If a + b is odd, then, for n > max (^^, ^, 4), m(t) = (2t + 1)(a + b), andc(t) = (2t + 1)((4n-7)a- critical graphs with average degree r. b), the family Q(a,b,n) = ^ S(n,m(t), c(t)) contains g - 1-crossing- Proof. For G G Q(a,b,n), let t be such that G G S(n,m(t),c(t)). As m(t) > 4g) and m(t) is odd, Proposition 5.1 implies that G is an (g) - 1)-crossing-critical graph. By construction, G has n3 = 4(2m(t)- 1)(n- 2)- 2c(t) vertices of degree three and n4 = m(t) + c(t) vertices of degree four. A short calculation establishes that the average degree of G is r. Details can be found in [19]. ? 5.2 Average degree six 57 2w + 1 subtiles . (a) A B C P1 Pi Qi Ri Si Pi+1 S2w+1 D E F G (b) Figure 5.2: (a) The tile Hw, w = 1. (b) An optimal tile drawing of H0. Demanding the average degree of oS(m, n, c) to be r = 3 + §, 1 < a < b, a + b even, forces m(t) to be an even number. The pattern in the staircase sequences is broken at the join of the first and the last tile and the resulting graphs are no longer critical. For such r, a more involved construction is needed. 5.2 Graphs with average degree close to six Let Hw be a tile, which is for w = 1 presented in Figure 5.2 (a). It is constructed by joining two subtiles, denoted by dashed edges, with a sequence of 2w + 1 subtiles, of which one is drawn with thick edges. The left (right) wall vertices of Hw are colored black (white). Hw is a perfect planar tile. Let H(w, s) = (Hw,..., Hw) be a sequence of tiles of length s and let H(w, s) = o(H(w, s)I) be the cyclization of its twist. Proposition 5.3. The graph H(w, s) is a crossing-critical graph with crossing number k = 32w2 + 56w + 31 whenever s > 4fc - 1. Proof. We define the following sets for 1 < i,p < 2w + 1, p = 2w + 1 and note their sizes: 58 Constructions Aw = {{A,Pi},{A,Qi},{A,Ri},{A,Si}\li U Qw,i U TZWyi U Sw>i) is an aligned family in Hw. The sets in the union are pairwise disjoint, thus \HW\ equals the sum of their sizes: \HW\ = 5-8w + 29 + J] (4 (8w - 4z) + 16) + 2 i=\ 2w 64w2 + 72w + 31- 16 ^ i %=\ 32w2 + 56w + 31 k. _ _ _ 5.3 Adapting graphs 59 The corresponding family H'w in Hi is twisted and propagates in H(w, s)*. Figure 5.2 (b) presents an optimal tile drawing of H0, its generalization to w > 0 demonstrates that H'w saturates Hlw. The crossing number of H(w,s) is established by Corollary 4.10. The number of crossings can be decreased after removing any edge from the drawing in Figure 5.2 (b). This also applies to the generalization of the drawing, thus Hw is a fc-degenerate tile. The propagation of the twisted family T' demonstrates tcr (®(H(w, s)*/«)) > k for any % = s, thus H(w, s)I is a k-critical sequence and the criticality of H(w, s) follows by Corollary 4.7. ? 5.3 Adapting graphs For d, d! > 3, let Kd>d> be a properly 2-colored complete bipartite graph: vertices of degree d are'colored black and vertices of degree d! are colored white. For p > 1, let the family K(d, d',p) consist of graphs with 2-colored vertices, obtained as follows: K(d,d', 1) = {Kd>d,} and K(d,d',p) = \JG&i(d,d>,P-i) GVlQV2 Kd>d>, where vx (respectively, v2) is a black vertex in G (Kd>d>). Ifd = d' = 3, we allow Vi to be any vertex. We preserve the colors of vertices in the zip product, thus the graphs in K(d, d',p) are not properly colored for p > 2. Proposition 5.4. Let d, d' > 3. Then every graph G G K(d, d', p) is a simple 3-connected crossing-critical graph with cr(G) = pcr(Kdtd,). Proof. By induction on p and using Theorem 3.7 (iii), we show that all black vertices of G are active. Iterative application of Theorem 3.7 (i) and (ii) establishes the crossing number of G and its criticality. For d = d' = 3, the claim follows similarly by Theorem 3.8. D Jaeger proved the following result: Theorem 5.5 ([56]). Every 3-connected cubic graph with crossing number one has chromatic index three. We use the family TZ(3, 3,p) to show that a similar result cannot be obtained for any crossing number greater than one. Proposition 5.6. For k > 2, there exist simple cubic 3-connected crossing-critical graphs with crossing number k and with no 3-edge-coloring. Proof. Let P be the Petersen graph. It is cubic, 3-connected, and has no 3-edge-coloring. Its crossing number is two and it is crossing-critical, since it is edge-transitive. The claim thus holds for k = 2. 60 Constructions zero, the coloring c represents a nonzero Z2 x Z2-flow on Gk. Thus, the sum of Z2 x Z2-flow rtir For k > 3, let G G 71(3, 3, k - 2) be arbitrary and let Gfc be a zip product of G and P. Since every vertex in P has two coherent bundles, Theorem 3.8 and Proposition 5.4 assert that Gk has crossing number k and is crossing-critical. It is 3-connected by Lemma 3.6 (ii). Suppose Gfc has a 3-edge-coloring c. We may assume the colors are nonzero elements of the group Z2 x Z2. Since the colors around every vertex add up to presents a colors on any edge-cut of Gk is zero. In particular, the three edges that result from the zip product of G and P receive distinct colors. This implies existence of a 3-edge-coloring of P, a contradiction. D Graphs with the above properties can be constructed also as zip products of k copies of the Petersen graph. The resulting graph has crossing number 2k. A zip product of such graph with crossing number k and any planar cubic graph has all the stated properties, except it is not crossing-critical. Thus, for every k > 2 there exists an infinite family of simple cubic 3-connected graphs with crossing number k and with no 3-edge-coloring. 5.4 Infinite families of crossing-critical graphs with prescribed average degree and crossing number In this section we prove the main result of this thesis: we settle Question 2.14. Theorem 5.7. Let r G (3,6) be a rational number and k an integer. There exists a convex continuous function f : (3,6) -»¦ E+ such that for k > f(r) there exists an infinite family of simple 3-connected crossing-critical graphs with average degree r and crossing number k. Proof. We present a constructive proof for A sketch of the construction is as follows: The graphs are obtained as a zip product of crossing-critical graphs from the families S and K, and of the graphs H, defined in Sections 5.1-5.3. The graphs H allow average degree close to six and the graphs from S allow average degree close to three. A disjoint union of two such graphs consisting of a proportional number of tiles would have a fixed average degree and crossing number. The zip product compromises the pattern needed for fixed average degree, for which we compensate with the 5.4 Infinite families 61 graphs from Tl. Their role is also to fine-tune the desired crossing number of the resulting graph. More precisely, let ?(n, m, c, w, s,p, q) be the family of graphs, constructed in the following way: first we combine graphs Gx E S(n,m,c) and G2 = H(w,s) in the family ?(n,m,c,w,s,0,0) = \Jg1g2UViv2giv1Qv2 G2. Further, we combine the graphs Gx E ?(n,m, c, w, s00) and G2 E 71(3, 3,p) in the family ?(n,m,c,w,s,p,0) = \Jg1g2Uv1v2givi®v2 G2. Finally, we combine the graphs Gx E ?(n,m,c,w,s)p0) and G2 E K(3,5,q) in the family ?(n,m,c,w,s,p,q) = \Jg1g2Uv1v2giv1®v2 G2. In each case, vt E V(Gt) is any vertex of degree three. Propositions 5.1, 5.3, and 5.4 imply that the graphs used in construction are crossing-critical graphs whenever the following conditions are satisfied: n > 3, m = 2m'+ 1, m! > 2 c > 0, c < 2m(n-3), w > 0, s > 4(32w2 + 56w + 31), p > 1, and q > 1. (5.1) (5.2) (5.3) (5.4) (5.5) (5.6) (5.7) (5.8) (5.9) All vertices of degree three in these graphs are semiactive. Results in [65] establish cr(K3,5) = 4, thus Theorem 3.8 implies that subject to (5.1)–(5.9) the graphs in ?(n, m, c, w, s, p, q) are crossing-critical with crossing number k Their average degree is f +32w 2 + 56w+p + 4o + 30. d = 6 4(m'(6n - 11) + 3n + 3p + 3q + 4s 7) 2m'(4n - 7) + 4n + 4sw + 9s + 4p + 6q 9 (5.10) (5.11) Using (5.10) we express p in terms of k and other parameters. We set s and m to be a linear function of a new parameter t, which will determine the size of the resulting graph. We substitute these values into (5.11). Using c we eliminate all the terms in the denominator that are independent of t. Parameter q plays the same role in the numerator. Then t cancels and we 2 _ c c 62 Constructions set the coefficients of the linear functions to yield the desired average degree. Finally, parameters n, w, and the constant terms of the linear functions are selected to satisfy the constraints (5.1)-(5.9). A more detailed analysis might produce a smaller lower bound /, but one constant term was selected to be zero to simplify the computations. More precisely, let r = 3 + §, 0 < a < 36, and k > /(r). Perform the following integer divisions: b"(b"+5) 2 6 b' 46 86(46 + 7) 6'a + 6r, 46"+ 6^, 6(36-a)+6r, and fc'(2&" + 5) + kr. For some integer t set n mt c w St = p = k q = 26" b" + 4, 2t(276 - 9a - 46r) - 2k' + 3, 2k' - 126" - 6kr - 33, 6, 2t((46" + 9)a-6), b,,(^+23) + 86(46 + 7) + 4k r + 56) , and kr + 5. The family T(a,b,k) = ZkT(n^mt^,w,st,p,q) is an infinite family of crossing-critical graphs with average degree r and crossing number k. Verification of the constraints (5.1)-(5.9) for any r G (3,6) and k > /(r) requires some tedious computation that is omitted here; an interested reader can find it in [19]. The function / is a sum of functions that are convex on (3,6) and thus itself convex. The graphs of T(a, 6, k) are 3-connected by Lemma 3.6 (ii). D The convexity of the function / in Theorem 5.7 implies iVj = max{/(n), /(r2)} is a universal lower bound on k for rational numbers within any closed interval/=[n,r2] C (3,6). 5.5 Structure of crossing-critical graphs _ _ _ k _ _ _ _ Oporowski has established that all large 2-crossing-critical graphs are obtained as cyclizations of long sequences, composed out of copies of a small number 5.5 Structure of crossing-critical graphs 63 Figure 5.3: Structure of known large k-crossing-critical graphs. of different tiles [87]. The construction of crossing-critical graphs using zip product demonstrates that no such classification of tiles can exist for k ? 4: by a generalized zip product of a graph and a tile, as proposed in Section 4.3.5, one can obtain an infinite sequence of k-degenerate tiles, all having the same tile crossing number. These tiles in combination with corresponding perfect planar tiles yield k-crossing-critical graphs. For k large enough, one can obtain k-crossing-critical graphs from an arbitrary (not necessarily critical) graph that has a vertex cover consisting of semiactive vertices of degree three, cf. Theorem 3.9. Figure 5.3 sketches the described structure. Regarding the degrees of vertices in k-crossing-critical graphs, the following questions remain open: Question 5.8 ([105]). Do there exist an integer k > 0 and an infinite family of (simple) 5-regular 3-connected k-crossing-critical graphs? Question 5.9. Do there exist an integer k > 0 and an infinite family of (simple) 3-connected k-crossing-critical graphs of average degree six? Arguments of [105] used to establish that for k > 0 there exist only finitely many k-crossing-critical graphs with minimum degree six extend to graphs with a bounded number of vertices of degree different than six. Thus, we may assume that a family positively answering Question 5.9 would contain graphs with arbitrarily many vertices of degree larger than six. But only vertices of degrees three, four, or six appear arbitrarily often in the graphs of the known infinite families of k-crossing-critical graphs. We thus propose the following question, an answer to which would be a step in answering Questions 5.8 and 5.9. 64 Constructions Question 5.10. Does there exist an integer k > 0, such that for every integer n there exists a 3-connected k-crossing-critical graph Gn with more than n vertices of degree distinct from three, four and six? We can obtain arbitrarily large crossing-critical graphs with arbitrarily many vertices of degree d, for any d, by applying the zip product to graphs K3,d, Kd,d, and the graphs from the known infinite families. However, the crossing numbers of these graphs grow with the number of such vertices. Chapter 6 The crossing numbers of Cartesian products In this chapter, we apply the zip product to establish lower and upper bounds on the crossing numbers of Cartesian products of some graphs with trees. We obtain several new exact results. 6.1 General graphs Let G« be the suspension of order % of a graph G, i.e. the complete join of G and an empty graph on % vertices {vu...,Vi}, called the apices of G«. For a multiset L C V(G2), we denote with Gx UL G2 the capped Cartesian product of graphs Gx and G2, i.e. the graph obtained by adding a distinct vertex v' to Gi D G2 for each copy of a vertex v G L and joining v' to all vertices of d D {w}. We call v' a cap of w. When L contains precisely all vertices of degree one in G2, we use Gx 6 G2 in place of G: DL G2. For t; G V(H), let Xz» denote the multiplicity of v in L and let L(v) := degG2(w) + Xl(v). An edge to G L(G2) is unbalanced if L(«) ^ €(w). Let /3(G2) be the number of unbalanced edges of G2. Theorem 6.1. Let T be a tree, L C V (T) a multiset with L(v) > 2 for every v G V{T), and G a graph of order n with a dominating vertex. Define B= Y, cr(G^)). veV(T) Then, B < cr(G DL T) < B + ^(T)^"1) and cr(G DL T) = B whenever the automorphism group of G acts as a symmetric group on the neighbors of the dominating vertex of G. 65 66 Cartesian products Proof. Let L = L(V(T)) be the set of different values of L(v), v G V(T). For / G L, let D® be a fixed optimal drawing of G«. Let vl}..., vm be some depth-first search ordering of vertices of T, set k = L(vi), and let e* = viUi be the edge connecting Vi with T[{v1}..., v^}]. Using this setup we construct G UL T as a sequence of zip products of suspensions of G. Let Gx = G and for % = 2,... ,m define d = G&> QH Gi_i, where a maps a vertex of the G subgraph of G&> to its counterpart in the neighborhood of some cap v! of m, u' G y(Gi_i). The graph Gm is isomorphic to G UL T. Since G has a dominating vertex, the apices in the suspensions have two coherent bundles. Iterative application of Theorem 3.4 implies cr(G DL T) > B. With the drawings L>«, we construct a drawing of G UL T that establishes the upper bound. We define D0 = D^ and, for % = 2,..., m, let A = L>&> ©ti A-i. If the symmetry condition is satisfied, then we can avoid introducing new crossings in the zip product of the drawings by Lemma 3.1. Also, if the edge van is balanced, then there is an apex in D^ that has the same vertex rotation as some cap of m in A-i. We perform the zip product using this apex and by Lemma 3.1 we introduce no new crossings. If neither of the conditions is satisfied, then Lemma 3.2 asserts that at most f^1) new crossings need to be introduced. The claim follows. D If G has no dominating vertex, then the apices of G« have two coherent bundles only for % > 3. The following more general version of Theorem 6.1 follows using the same arguments as in its proof. Theorem 6.2. Let T be a tree of order m, L C V (T) a multiset with L(v) > 3 for every v G V (T), and G a graph of order n. Define B = vv(T) cr(G^v))). v&V Then, B < cr(G DL T) < B + ß(T)n-L and cr(G ULT) = B whenever the stabilizer subgroup ?(v) of the automorphism group of G acts as a symmetric group on V(G) \ {v} for some v G V (G). In the rest of Chapter 6, we list several special cases of the above theorems. The following two corollaries imply equality of cr(G D Pm) and cr(G D Pm) up to an additive constant. Corollary 6.3. cr(G D Pm) = (m + 1) cr(G(2)) for a graph G with a dominating vertex andm>0. Proof. For G D Pm, the multiset L contains precisely the two vertices of Pm of degree one. The claim follows by Theorem 6.1, since all edges of Pm are balanced. ? 6.2 Cycles 67 Corollary 6.4. The following inequality holds for a graph G of order n with a dominating vertex and m>2: (m - 1) cr(G^) < cr(G D Pm) < (m - 1) cr(G^) + 2 fcr(G«) + fn " 1 V Proof. G U Pm contains G D Pm_2 as a subdivision, thus cr(G D Pm) > (m - 1) cr(G(2)) by Corollary 6.3. Let u,v be the caps of G = GUPm_2 and t/, v" the apices of two disjoint copies G', G" of G«. We observe that GDPm is isomorphic to some graph in (Gu©„/ G') „©„" G" and the claim follows by Lemma 3.2. D 6.2 Cycles Lemma 6.5. Whenever (i) 3 < n and 1 < d < 6, (ii) 3 < n < 6 and 1 < d, (iii) 3 < n < 8 and 1 < d < 10, or (iv) 3 < n < 10, 1 < d < 8, then cr(Gid)) = [f J [^-\ [|J [^J and, moreover, there exists an optimal drawing of C{f> in which the vertex rotation around every apex respects the cyclic ordering imposed by Cn. Proof. The graph C^ has Kn>d as a subgraph, thus cr(Gid)) > cr(Kn4). Kleitman established the crossing number of the latter when (i) or (ii) apply [65], and Woodall established it under conditions (iii) or (iv) [134]. In each of the cases, we can add the edges of the cycle into an optimal drawing of Kn>d without introducing new crossings, cf. Figure 6.1 for an example with n = 7, d = 3. The vertex rotations around the apices in these drawings respect the ordering imposed by G„. ? Corollary 6.6. Let d be the maximum degree in a tree T and n an integer. If one of the conditions (i)-(iv) applies to n, d, then, for dv = degT(w), v E V(T), cr(GraDT)= V - ^—11 I —I I^LH1l . (6.1) ^2 222 V&V(T) Proof. The proof follows the arguments of the proof of Theorem 6.2, using consistency of vertex rotations around apices in optimal drawings of C{nd) implied by Lemma 6.5. The major distinction are vertices of degree one and two in T, since the apices of the graph cL2) have only one coherent bundle. But Gi2) is planar, and Lemma 3.5 applies. Equality (6.1) follows by Lemma 6.5. D 68 Cartesian products #1,3,3 ^3 (2) #1,2,7 wY Figure 6.1: Several optimal drawings. 6.3 Stars The graph S^ is isomorphic to the complete tripartite graph KlAn, which can be obtained by contracting an edge of Kd+hn+1. Also, the graph Sn D Sd is a subdivision of S^. These observations enable us to express the crossing numbers of Cartesian products of stars with trees as a sum of the crossing numbers of Cartesian products of two stars: Corollary 6.7. Let T be a tree andn>1. Then, for dv = degT(w), cr(Sn D T) J2 cr(#lA,n)- veV(T), dv>2 Proof. Let V be the tree obtained by deleting all the leaves of T and let L be the set of leaves of T', each leaf v with multiplicity equal to degT(w) - 1. The graph Sn D T is a subdivision of Sn UL V and the claim follows by Theorem 6.1 since S{nd) is isomorphic to K1An. D Corollary 6.8. Let n ? 1 be any integer and T a subcubic tree with n2 vertices of degree two and n3 vertices of degree three. Then, cr(Sn D T) Let T be a tree. Then, cr(S3 ü T) = (n2 + 2n3) ------- + n3 ) ^ d J / dv - 1 \ — 2 —----- +1 2 2 v&V(T), dv>2 (6.2) (6.3) _ _ 6.4 Wheels 69 Proof. Asano proved cr(X1)3)„) = f 2 2f± + 1 in [10]. The equation (6.3) follows by Corollary 6.7.' ' The graph Klt2,n has K^n as a subgraph. Kleitman [65] proved that cr(X3)„) = [2j [s^lj. Figure 6.1 presents a drawing of Klt2,n with this many crossings (n = 7). Another application of Corollary 6.7 yields (6.2). D A special case of (6.2) was conjectured by Jendrol’ and ˇčerbova [57]. Corollary 6.9. cr(Sra D Pm) = (m - 1) [f J [^J for m, n > 1. 6.4 Wheels We introduce another operation on graphs that allows us to study the crossing numbers of Cartesian products of wheels. Let F C E(G) be a subset of edges of G and vr a permutation of F. A vr-subdivision Gn of G is the graph, obtained from G by subdividing every edge e G F with the vertex we and adding the edges {vev 3. Then cr(G") > cr(G) + 1, (6.4) with equality ifn respects the edge rotation around v in some optimal drawing ofG. Proof. Let Cv be the cycle on the edges {vevn{e) | e G F} in G\ Let Dn be an optimal drawing of Gn and D the induced subdrawing of G. The triple (v, Bv, Cv) is a wheel gadget of degree |F| > 3 in G\ Assume it has no crossing on G„ in D*. Then G„ is a simple closed curve in D* and the whole drawing D* lies in the same component of ? - G„. Without loss of generality, D* lies in the exterior of the disk bounded by Cv and by Lemma 4.14 an inner spoke must cross an outer spoke. Let c be the number of crossings on the inner spokes. Claim 1: Under the above assumptions, cr(D) > cr(G) + c - I ^ . Let e be some inner spoke with the smallest number of crossings. We draw a new vertex u in the interior of Cv. It is possible to connect u with all vertices of Cv without introducing new crossings and also todetach e from its endvertex on Cv and connect it with u (crossing G„). Let D* be the modified drawing, presented in Figure 6.2, and let D be its subdrawing obtained by removing the rim and all inner spokes but e from D*. In Figure 6.2, we indicate D with 70 Cartesian products Figure 6.2: Drawings D* and D. the solid edges. Since D is a drawing of a subdivision of G and has at least 1^1 crossings less than D, the claim follows. Either there is a crossing of D* on C„, which is not present in D, or c 1^1 ? 1. Inequality (6.4) follows. If vr respects the edge rotation around v in an optimal drawing D of G, we can draw Cv in L> with at most one new crossing. D Lemma 6.11. cr(W4 j) = 2 J L 2 (2) J + 1 for n > 3. Proof. The drawing of G = wi2) with k = [f J [^J + 1 crossings presented in Figure 6.1 (with n = 7) establishes the upper bound. Let D be an optimal drawing of G for some n > 3. Partition the edges of G into the edges Ex of the X3>ra subgraph of G, the edges L2 of the path between the apices u, v of G containing the center w of the wheel, and the edges E3 of the rim. There are at least k - 1 crossings between the edges of Ex. If there is a crossing involving an edge of E3, the claim follows. Otherwise the rim is drawn as a simple closed curve 7 and we may assume that G is drawn in the disk ? bounded by 7. The edges emanating from each of the vertices u, v, and w do not cross and separate ? into n disks. For distinct x,y G {u,v,w}, there are at least [fj [2=±J crossings between edges incident with x and y, implying a contradiction cr(L>) > 3(fc - 1). D Corollary 6.12. cr(Wn D Pm) n>3. (m - 1) (|JJ [2fiJ + 1) + 2 for m > 1 and c c _ Proof. Two applications of Theorem 6.10 to the graph with two vertices and n + 1 parallel edges among them prove the claim in case m = 1. 6.4 Wheels 71 Let u, v be the caps oW = WnD Pm-2 and let Fu (respectively, Fv) contain the edges incident with u (v) and a vertex on the rim of the corresponding wheel in G. Corollary 6.3 and Lemma 6.11 assert cr(G) = (m - 1) ([f J [^J + 1). The graph Wn D Pm is isomorphic to G' = (Gn)n' for properly chosen permutations vr of Fu and vr' of F„. Theorem 6.10 implies cr(G') = cr(G) + 2. D Lemma 6.13. cr(W3w) = 5. Proof. Let G = W^, let L> be an optimal drawing of G, and let G be the set of edges of the rim of W3. In D, there is no crossing between two edges of G. These therefore bound a disk ? in D. Then G-C = S^] and let F be the set of edges of S3 in G - G. The result of Asano [10] implies at least three crossings on the edges of G - G. If there are two crossings on G, the claim follows. Assume there is only one crossing on G. If it is a crossing with an edge of F, then the induced drawing of G - F has no crossing on G and we may assume it lies in the interior of ?. The graph G - F - C is isomorphic to the graph K3A, of which three vertices are incident with G, and four are not, say v1}.. .,v4. The edges emanating from Vi and v j must cross for distinct i,j?{1,2,3,4}. This implies at least six crossings in D. Assume the only crossing on G is not a crossing with an edge of F, but with an edge e emanating from one of vi, % ? {1, 2, 3, 4}. The induced drawing of G - e has no crossing on G, thus we may assume it is drawn in the interior of ?. By the argument of the previous paragraph, there are at least three crossings between the edges of K3)3 subgraph of G - Vi - C. If there is an additional crossing on the edges incident with Vi distinct from e, the claim follows. Assume there is none. Then there exists a simple closed curve 7 that starts at the center w of the wheel, follows the edge wvi, continues along an edge connecting Vi with the rim G, along the edges of G, along the other edge connecting Vi and G, and finally closes along Viw, such that G - Vi - C is drawn inside the disk ?' bounded by 7. The vertex w is incident with other three vertices on the boundary of ?' and we may assume two of the edges lie on this boundary. Let / be the third of these edges, which separates the other two neighbors of win ?'. There is a drawing of K2A in ?' with four vertices on the boundary of ?', which has at least two crossings on its edges and at least two crossings with /. If there are no crossings on G, then we may assume the whole drawing, and in particular the subdrawing of KA>3, is in ? and has at least six crossings. 72 Cartesian products The claim about cr(W3)3) follows, since Figure 6.1 presents a drawing of Wp with five crossings. ' ? Corollary 6.14. Let T be a subcubic tree with m vertices of degree i, % = 1, 2, 3. Then, cr(W3 UT) = nx + 2n2 + 5n3. Proof. We remove all the leaves from T and obtain a tree V. Let L be the multiset of leaves of T', each v G L with multiplicity equal to degT(w) - 1. Thus, L(v) with respect to L and V equals degT(w), which is at least two for every v G V (T'). Since Lemmas 6.11 and 6.13 establish cr(Vy3(2)) = 2 and cr(Vy3(3)) = 5, Theorem 6.2 implies cr(W3 UL V) > 2n2 + 5n3. Equality follows as the vertex rotations are consistent in the optimal drawings of W3(2) and W3(3) in Figure 6.1. This consistency in combination with Theorem 6.10 also implies that a properly chosen vr-subdivision of edges connecting a cap of W3 UL T with the corresponding rim increases the crossing number by precisely one. To obtain W3 D T from W3 UL T, we need one such subdivision for each leaf of T, and the claim follows. ? Part III The Minor Crossing Number 73 Chapter 7 Preliminaries Two minor-monotone variations of the crossing number invariant are presented in this chapter. They are derived from the ordinary crossing number using general principles of how a graph invariant can be transformed into a minor-monotone graph invariant, as studied by Fijavˇz [38]. One of the variations bounds the crossing number of a graph from above and the other bounds it from below. As the minimization of the number of crossings and lower bounds on this number are of more general interest, only this second variation is studied in greater detail. The results of this chapter are based on research conducted by Fijavˇz, Mohar, and the author [20]. Only few results relating graph minors and the crossing numbers of graphs have been published prior to this work. Moreno and Salazar presented a lower bound on the crossing numbers of graphs in terms of their minors with a small maximum degree [86]. This result is generalized in Section 8.1. Robertson and Seymour [109] determined the forbidden minors for being a minor of a graph having crossing number at most one. The minor crossing number introduced in the following section generalizes this concept; these graphs are the forbidden minors for having minor crossing number at most one. The structure of drawings used to obtain this result is generalized to graphs with larger minor crossing numbers and applied in Chapter 9 to improve a lower bound on the minor crossing number of a graph using the number of its edges. Another related result is the proof of Hlinˇen´y that shows the crossing number problem is NP-hard for cubic graphs [55]. As subdivisions of graphs (which do not affect crossing numbers) are equivalent to minors for cubic graphs, this result implies that the minor-monotone variant of the crossing number problem is NP-hard. The fact that for a cubic graph the crossing number equals the minor crossing number generates additional interest to studying the crossing numbers of such graphs. Some research in this direction was conducted by McQuillan and Richter [81, 98]. 75 76 Preliminaries 7.1 Definitions and basic lemmas For a given graph G, the minor crossing number is defined as the minimum crossing number over all graphs that contain G as a minor: mcr(G, E) := min {cr(H, E) | G 0 be an integer and E a surface. The families u(k, E) and fl(k, E) are minor-closed. For eachgraph G, there exists a graph G such that mcr(G, E) = cr(G, E) and G 3, then G can be obtained from H by contracting edges only. Further, if G is simple, then H is simple, otherwise there exists a simple cubic realizing graph H' ofG. Proof. Let H0 be a realizing graph of G without removed edges and let D0 = {tp,e) be an optimal drawing of H0. We shall describe H in terms of its drawing D obtained from D0. For each vertex v of H0 of degree d := degH[>) + 3, let Uv be a closed disk containing 3, d = 2, and d = 1, we modify D0 in [/„ as indicated in Figure 7.2. Let D be this new drawing and H the graph defined by D. Clearly, G mcr(G,E). The fact that D contains no new crossings implies mcr(G, E) = cr(H0,E) = cr(L>,E) > cr(H,E). A combination of these two inequalities proves cr(H, E) = mcr(G, E). If 5(G) > 3, then we can assume 6(H0) > 3. This implies \E(H)\-\V(H)\ = \E{H0)\ - \V{H0)\. Since H0 N by setting w(G,H,e) = 0 if e G R and w(G,H,e) = 1 if e G E(G). If e G C, then let Tv be the maximal tree induced by C containing e. Let Tx and T2 be the components of Tv - e and let di, % = 1,2, denote the number of edges in E(G) incident with T*. Set w(G, H, e) = min{di, d2}. For e G E(H), we call w(G, H, e) the weight of e. Let G Hu f) = E/eEl-e W(G, H, /) = w(G, H, e) and to each crossing x of e with some e' in Dx correspond exactly the crossings of Ex - e with the edge e', the inequality (8.1) follows. ? Theorem 8.3. Let G be a minor of a graph H, ? a surface, and r := |j?(G)J. Then, cr(G,?) g(G)-g(?) andmcr(G,?) >g(G)-2g(?). If ? is a nonorientable surface with genus g(?), then mcr(G, ?) > g(G) - Proof. Let D be an optimal drawing of a realizing graph G in an orientable surface ?. For each crossing in D, we add a handle to ? and obtain an embedding of G in a surface ?' of genus g(?') = g(?) + mcr(G, ?). Using minor operations on D, we can obtain an embedding of G in ?', which yields #(?') > g(G). Thus, we have mcr(G, ?) > g(G) - g(?). The other two claims can be proven in a similar way by adding crosscaps at the crossings of D. Note that adding a crosscap to an orientable surface of genus g results in a surface of nonorientable genus 2g + 1. D When the genus of a graph is not known, one can derive the following lower bound using the Euler Formula and the same technique as in the preceding proof. Proposition 8.7. Let G be a graph with n = \V(G)\, m = \E(G)\, and girth rand let ? be a surface of Euler genus g. Then, mcr (G, ?) > ^m-n-g + 2. Proof. As in the proof of Theorem 8.6 we obtain an embedding D of G in Nfl+fc, where k = mcr(G,?). Let / be the number of faces in D. All faces have length at least r, thus / < ^. The Euler Formula results in 2-(g + k) = n-m + f 1 bean integer. Then, for any I G {1,... , k}, the family to (k, E) consists precisely of all those graphs G E u(k - l,N9+l) for which there exists a graph G that contains G as a minor and that can be drawn in the nonorientable surface Ng+t of Euler genus g + / with (orienting) degeneracy (k-l,l). Proof. Let G G u(k, E) and let G be its realizing graph, drawn in E with at most k crossings. Choose a subset of / crossings of G. By replacing a small disk aroundeach of the chosen crossings with a Möbius band, we obtain a drawing of G in Nfl+I with (orienting) degeneracy (k-l,l). The replacement at one such crossing and the corresponding curve annihilating the crosscap are illustrated in Figure 9.1. For the converse, we first prove the induction basis / = 1. Let G be the graph that contains G as a minor and is drawn in Ng+l with at most k - 1 crossings and let us assume that an (orienting) onesided curve 7 intersects the drawing of G in at most two points, x and y. After cutting the surface along 7 and pasting a disk A on the resulting boundary, we get a surface of Euler genus g. On the boundary of A, two copies of x and y interlace. By adding paths Px and Py to join the copies of x and y, respectively, we obtain a drawing D' of a graph G', which contains G (and hence also G) as a minor. Clearly, D' is a drawing in E and has one crossing more than the drawing of G (the one between Px and Py). As D' has at most k crossings, G G u{k, E). 9.2 Structure theorem 87 \ \ \ \ i i 1 \ i / / / / i \ i \ \ \ / / Figure 9.1: Replacing a crossing by a crosscap and a respective annihilating curve. If / > 2, we may annihilate the crosscaps consecutively since the curves in the corresponding /-system are noncrossing. Note that if the /-system is orienting, we obtain an orientable surface ?. ? Lemma 9.3. Let G be a graph with an (orientably) k-degenerate embedding in a surface ?. If G is a surface minor of G, then G is also (orientably) k-degenerate. Proof. It suffices to verify the claim for edge-deletions and edge-contractions. For edge-deletions, there is nothing to prove. For edge contractions, we verify that a fc-system for G can be transformed into a fc-system for G/e, e = uv. Let ? be a fc-system of G and let ?e C ? contain the curves of ? that intersect e. If 7 G ?e intersects e twice, we may replace 7 in ? by a curve that does not intersect G at all. We may thus assume that each 7 G ?e intersects e exactly once. Let t = \?e\, let xu...,xt be the points of intersection of e with curves in ?e, and let x0 = u, xt+i = v. By contracting segments XiXi+l, % = 0,... ,t we obtain an embedding of G/e in which the curves of ?e are modified to touch at the new vertex, obtained by the contraction of e. Thus, the modified curves of ? form a fc-system of G/e. D If we restrict edge-contraction to edges that are not involved in crossings, Lemma 9.3 can be extended to drawings with crossings. 9.2 Structure theorem A direct consequence of Lemmas 9.2 and 9.3 is the following: Theorem 9.4. Let ? be an (orientable) surface ofEuler genus g and let k > 1 be an integer. Then, u(k,?) consists of precisely all the graphs that can 88 Structure of graphs with bounded mcr(G, ?) X] fx [X (a) (b) (c) Figure 9.2: Embeddings in the Klein bottle with orienting degeneracy 2. be embedded in the nonorientable surface Ng+k of Euler genus g + k with (orienting) degeneracy k. Proof. Let G be embedded in N9+k with (orienting) degeneracy k. Then Gcü(k, ?) by Lemma 9.2. G T Let G G Lü(k, ?). By Lemma 9.2, there exists a graph G G w(fc, ?) that has G as a minor and has a fc-degenerate embedding in Nfl+fc. Then G has such embedding by Lemma 9.3. ? Figure 9.2 (a) exhibits the geometric structure of a realizing graph in the Klein bottle, (b) shows the general structure of its minors G with mcr(G) < 2, and (c) is a degenerate example of this structure in which the curves of the corresponding 2-system {71,72} touch twice. Theorem 9.4 can be used to express a more intimate relationship between the graphs in u(k, ?) and u(0, ?). Corollary 9.5. Let ? be a surface of Euler genus g,k>0an integer, and let G G Lü(k, ?). Then there exists a graph H, which embeds in ?, such that G can be obtained from H by identifying at most k pairs of vertices. Proof. Let G G u(k, ?). Then G has an (orientably) fc-degenerate embedding in Nfl+fc by Theorem 9.4. Let ? be a corresponding (orientable) fc-system. We may assume that all the intersections of curves in ? with G are at the vertices of G, thus each 7 G ? intersects G in at most two vertices. Assume first that ? = {7} and that 7 intersects G at the vertices u, v. We cut Nfl+i along 7 and paste a disk ? to the boundary of the cut surface. We thus obtain an embedding of a graph G' in ? that has the vertices u,v,u',v' on the boundary of ?. We add the edge uu' and contract it to obtain a graph H embedded in ?. Then G is obtained from H by identifying the vertices v and v'. 9.3 Improved bound 89 As the curves in ? are pairwise noncrossing, we may resolve the case |?| > 1 by induction. D 9.3 Improved bound Theorem 9.4 can be used to improve the lower bound of Proposition 8.7. Theorem 9.6. Let G be a simple graph with n = \VG\, m = \EG\ and let ? be a surface of Euler genus g. Then, mcr(G, ?) > \(m - 3(ra + g) + 6). We need two technical lemmas to prove this result. Let ? be a closed surface and x,y E ?. Let ? = {7l,... ,7fc} be a fc-system of onesided noncrossing simple closed curves in ? such that 7i n 7i = {x, y} for all 1 < i < j < k. Let li = l\ U it where ~{\ is an arc from x to y. If a curve ~{\ U 7™ (i = j) bounds a disk in ? whose interior contains no segment of curves in ?, then we say that ~{\ U 7™ is a ?-digon. Lemma 9.7. A k-system ? has at most k - 1 ?-digons. Proof. Let us contract one of the segments, say 7}. Then each other 7^ becomes a loop in ?. Since ? is a fc-system of onesided noncrossing loops, the loops in ? generate a fc-dimensional subspace of the first homology group #i(?;Z2). Therefore, the 2fc-1 loops L = {7^ | 1 4 requires additional arguments. Chapter 10 Applications to families of graphs In this chapter, we apply the lower bounds on the minor crossing number developed in the preceding chapters to several families of graphs. In general, Theorem 8.3 yields better bounds for graphs of small maximum degree (cubes, Cm D Cn), while Theorem 8.6 suits graphs with large maximum degree better, e.g. complete bipartite graphs. Theorem 9.6 performs best on dense graphs of girth three, e.g. complete graphs. 10.1 Complete graphs Both Theorem 8.6 and Theorem 9.6 imply the following inequality, which is sharp for ra G {3,..., 8}, as demonstrated in Figure 10.1: Proposition 10.1. mcr(Kn) > \\(n - 3)(n - 4)] for n > 3. The following proposition establishes an upper bound: Proposition 10.2. mcr(Kn) < [\(n - 5)2J + 4 for n > 9. Proof. We shall exhibit graphs Kn (n > 9) together with their drawings Dn so that Kn contains Kn as a minor and that cr(Dn) = [\(n - 5)2J + 4. Figure 10.2 presents drawings of Kw and Kn. Different vertex symbols (diamond, circle, triangle, etc.) represent vertices in the same tree Tv, v E V(Kn), which contracts to the vertex v in the Kn minor. By contracting the thick edges of the graphs in Figure 10.2, we obtain Kw and Kn, respectively. The reader shall have no difficulty placing the tree Tn+l into Dn in order to obtain Dn+1. The tree Tn+1 crosses precisely each Tv with 7 < v < n. To 91 92 Applications Figure 10.1: Realizing drawings of K6, K7, and K8. connect Tn+1 with the trees T1, . . . , T6, we need three new crossings if n is even (T1 with T2, T3 with T4, and T5 with T6) and no new crossing if n is odd. ~ Let cn denote the number of crossings in the drawing of Kn described above, and let ak = c2k. We have a4 = 6, a5 = 14, a6 = 26 and a recurrence equation, ak+1 = c2k+2 = c2k+1 + (2k - 1 - 6) = c2k + (2k - 6) + 3 + (2k - 1 - 6) = c2k + 4k -8 = ak + 4k - 8, whose solution is ak = 2k2 - 10k + 14. For even values of n, this yields and, for odd values of n, Ca = \((n - 5)2 + 3) cn = \(n- 5)2 + 4. D Corollary 10.3. Let ? be a fixed surface and cn = sequence {cra}~=3 is nondecreasing and, for ? = S0, Coo := lim cne \jA] ¦ 2^pforn>3. The Proof. We first prove the following claim: if mcr(Xra, ?) >cn(n-1), then mcr(Xm, ?) > cm(m - 1), for every m > n. It suffices to prove this for m = n + 1. Kn+1 in ?. Let T; be the tree in D which contracts to the vertex i of Kn+1. ? cm(m - — It suffices to prove this for m = n + 1. Let D be a realizing drawing of 10.2 Complete bipartite graphs 93 T3 T± Ti T2 T5 T6 ~~ Figure 10.2: Drawings of graphs K10 and K11. If we remove T; and all incident edges from D, we obtain a drawing of a graph with Kn minor. This can be done in n + 1 different ways. These n + 1 drawings contain at least (n + 1) mcr(Kn,?) crossings altogether. We may assume there are no removed edges in D, as their number can only increase the number of crossings. Each crossing from D then appears in at most n - 1 of these drawings. Therefore, (n - 1) mcr(Kn+l,?) > (n + 1) mcr(Kn,?) > c(n+1)n(n-1). The stated bounds on Coo for ? = §0 follow from Proposition 10.1 and Proposition 10.2. D We believe that the minor crossing numbers of complete graphs lie close to the upper bound from Proposition 10.2 and that the following asymptotic holds: mcr(Kn) 1 2 + 0(n). 10.2 Complete bipartite graphs The nonorientable genus of complete bipartite graphs [85] in combination with Theorem 8.6 establishes the following proposition: Proposition 10.4. mcr(Km,n) > \\(m- 2)(n - 2)] for3 3. Proof. Proposition 10.4 implies mcr(X3)ra) > [2=2] for n > 3 and mcr(X4)ra) > n - 2 for n > 4. Drawings, analogous'to those in Figure 10.3 (b) and (c), demonstrate these lower bounds are tight. ? Despite the fact that the lower bound from Proposition 10.4 is attainable for m = 3, 4, we believe that the upper bound from Proposition 10.5 lies closer to the actual minor crossing number: mcr(Xm)ra) = mn + 0(m + n) for m > 5. 10.3 Hypercubes _ Applying Proposition 8.7 to hypercubes yields 10.3 Hypercubes 95 :::iJ::TT:xJ::: :::J-t:T"r:±_t::: J" 1 Figure 10.4: A drawing of Q~5 with 64 crossings. Dashed edges correspond to the original edges of a matching between two Q~4 subgraphs. Proposition 10.7. mcr(Qra) > (n - 4)2ra"2 + 2 for n > 4. Proof. The graph Qn has v = 2n vertices, e = n2n~l edges, and girth r = 4. Proposition 8.7 implies mcr(Qra) > r-^e - v + 2 = (n - 4)2ra"2 + 2. D Combining the best known lower bound for crossing numbers of hypercubes cr(Qra) > 4720 - (n2 + 1)2ra"1 by Sykora and Vrto [121] with Corollary 8.4 we can deduce an alternative lower bound. It is stronger than Proposition 10.7 for large values of n: Proposition 10.8. mcr(Qra) > \ (\ 4ra - 2n+l) - 2n+l for n>4. Proof. In the graph Qn, vertices have degree n. Set r = [f J. By Corollary 8.4, we have mcr(Qra) > ^ cr(G) > ^ 1 4ra 2ra+l 2ra+1 - D As demonstrated in Figure 10.4, one can obtain a family of graphs Q~n and ~~ their drawings Dn with ?(Qn) = 4 and Qn having Qn as a minor. These, which were inspired by Figures 2 and 3 in [80], establish the following upper bound: 96 Applications Figure 10.5: A drawing of G7,9 with 30 crossings. Dashed edges correspond to the original edges of a cycle corresponding to C9. Proposition 10.9. mcr(Qra) < 2 • 4ra"2 - (n - 1)2ra"1 for n>2. Proof. Let a drawing Dn of a graph with Qn minor be iteratively designed as in Figure 10.4 and let q(n) be its number of crossings. Then q(3) = 0 and q(n) = 2q(n - 1) +2ri"1(2ri-3 - 1) for n > 3. Solving this recurrence relation establishes q(n) = 2 • 4ra"2 - (n - 1)2ra"1. D 10.4 Cartesian products of cycles Combining the results presented in [42] with Theorem 8.3 implies the following: Proposition 10.10. \(m - 2)n < mcr(Cm D Cn) for either 3 < m < 7, n>m,orm>7,n> \(m + 1)(m + 2). Figure 10.5 presents a drawing of the graph G7)9 whose generalization Gm,n, 33>n and K2An, J. Graph Theory 10 (1986), 1-8. [11] J. Balogh, G. Salazar, fc-sets, convex quadrilaterals, and the rectilinear crossing number of Kn, to appear in Discrete Comput. Geom. (2006). 97 98 BIBLIOGRAPHY [12] L. W. Beineke, R. D. Ringeisen, On the crossing numbers of products of cycles and graphs of order four, J. Graph Theory 4 (1980), 145-155. [13] S. N. Bhatt, F. T. Leighton, A framework for solving VLSI graph layout problems, J. Comput. System Sci. 28 (1984), 300-343. [14] D. Bienstock, N. Dean, Bounds for rectilinear crossing numbers, J. Graph Theory 17 (1993), 333-348. [15] D. Bienstock, N. Dean, New results on rectilinear crossing numbers and plane embeddings, J. Graph Theory 16 (1992), 389-398. [16] J. Blaˇzek, M. Koman, A minimal problem concerning complete plane graphs, in: M. Fiedler, ed., Theory of Graphs and Its Applications, Academic Press, New York, 1965, 333-338. [17] G. Bloom, J. Kennedy, L. Quintas, On crossing numbers and linguistic structures, in: M. Borowiecki, J. W. Kennedy, M. M. Syslo, eds., Graph Theory Proceedings, Lagow 1981, Lecture Notes in Math. 1018, Springer, Berlin, 1983, 14-22. [18] H. L. Bodlaender, A. Grigoriev, Algorithms for graphs embeddable with few crossings per edge, in: M. Liskiewicz, R. Reischuk, eds., Fundamentals of Computation Theory, Lecture Notes in Comput. Sci. 3623, Springer, Berlin, 2005, 378-387. [19] D. Bokal, Technical details regarding infinite families of crossing-critical graphs with prescribed average degree and crossing number, Mathematica™ notebook (2006), http://lp.fmf.uni-lj.si/~drago/construction3_6.nbor http://lp.fmf.uni-lj.si/~drago/construction3_6.pdf. [20] D. Bokal, G. Fijavˇz, B. Mohar, The minor crossing number, SIAM J. Disc. Math., to appear (2006). [21] A. Brodsky, S. Durocher, E. Gethner, Toward the rectilinear crossing number of Kn: new drawings, upper bounds and asymptotics, Discrete Math. 262 (2003), 59-77. [22] C. Buchheim, D. Ebner, M. Ju¨nger, G. W. Klau, P. Mutzel, R. Weiskircher, Exact crossing minimization, in: P. Healy, N. S. Nikolov, eds., Graph Drawing: 13 th International Symposium, Lecture Notes in Comput. Sci. 3843, Springer, Berlin, 2006, 386-396. BIBLIOGRAPHY 99 [23] F. M. Chockallingam, VLSI layout for the star connected cycles, Tech. Report, University of Nevada, Reno, 1996. [24] C. Chojnacki, Uber wesentlich unpl¨attbare Kurven im dreidimensionalen Raume, Fund. Math. 23 (1934), 135-142. [25] F. Chung, S. T. Yau, A near optimal algorithm for edge separators, in: F. T. Leighton, M. Goodrich, eds., Proceedings of the 26 th Annual ACM Symposium on Theory of Computing, ACM Press, New York, 1994, 1-8. [26] A. M. Dean, R. B. Richter, The crossing number of C4 D C4, J. Graph Theory 19 (1995), 125-129. [27] R. Diestel, Graph Theory, Graduate Texts in Mathematics, vol. 173, Springer, New York, 2000. [28] H. E. Dudeney, Amusements in Mathematics (1917), The Gutenberg Project, 2005, http://www.gutenberg.org/etext/16713. [29] R. Eckler, Dictionary eodermdromes, Word Ways, 1980. [30] R. B. Eggleton, R. K. Guy, The crossing number of the n-cube, Notices Amer. Math. Soc. 17 (1970), 757. [31] G. Elekes, On the number of sums and products, Acta Arith. 81 (1997), 365-367. [32] G. Elekes, Sums versus products in number theory, algebra and Erdos geometry, in: G. Hal´asz, L. Lov´asz, M. Simonovits, V. T. So´s, eds., Paul Erdos and His Mathematics II, Bolyai Soc. Math. Stud. 11, Springer, Berlin, 2002, 241-290. [33] G. Elekes, M. B. Nathanson, I. Z. Ruzsa, Convexity and sumsets, J. Number Theory 83 (1999), 194-201. [34] P. Erdos, R. K. Guy, Crossing number problems, Amer. Math. Monthly 80 (1973), 52-58. [35] G. Exoo, F. Harary, J. Kabell, The crossing numbers of some generalized Petersen graphs, Math. Scand. 48 (1981), 184-188. [36] L. Faria, C. M. H. de Figueiredo, On Eggleton and Guy conjectured upper bound for the crossing number of the n-cube, Math. Slovaca 50 (2000), 271-287. 100 BIBLIOGRAPHY [37] L. Faria, C. M. H. de Figueiredo, O. Sykora, I. Vrto, An improved upper bound on the crossing number of the hypercube, in: H. L. Bodlaender, ed., Graph-theoretic Concepts in Computer Science, Lecture Notes in Comput. Sci. 2880, Springer, Berlin, 2003, 230-236. [38] G. Fijavˇz, Grafovski minorji in povezanost, Dissertation, University of Ljubljana, 2001. [39] S. Fiorini, On the crossing number of generalized Petersen graphs, in: A. Barlotti, M. Biliotti, A. Cossu, G. Korchmaros, G. Tallini., eds., Combinatorics ’84: Proceedings of the International Conference on Finite Geometries and Combinatorial Structures, Ann. Discrete Math. 30, North-Holland, Amsterdam, 1986, 225-242. [40] M. R. Garey, D. S. Johnson, Crossing number is NP-complete, SIAM J. Algebraic and Discrete Methods 4 (1983), 312-316. [41] J. F. Geelen, R. B. Richter, G. Salazar, Embedding grids on surfaces, European J. Combin. 25 (2004), 785-792. [42] L. Y. Glebsky, G. Salazar, The crossing number of Cm D Cn is as conjectured for n > m(m + 1), J. Graph Theory 47 (2004), 53-72. [43] H. H. Glover, J. P. Huneke, Cubic irreducible graphs for the projective plane, Discrete Math. 13 (1975), 341-355. [44] H. H. Glover, J. P. Huneke, C.-S. Wang, 103 graphs that are irreducible for the projective plane, J. Combin. Theory Ser. B 27 (1979), 332-370. [45] M. Grohe, Computing crossing numbers in quadratic time, J. Comput. System Sci. 68 (2004), 285-302. [46] R. K. Guy, Latest results on crossing numbers, in: M. Capobianco, J. B. Frechen, M. Krolik, eds., Recent Trends in Graph Theory, Lecture Notes in Math. 186, Springer, Berlin, 1971, 143-156. [47] R. K. Guy, The decline and fall of Zarankiewicz’s theorem, in: F. Harary, ed., Proof Techniques in Graph Theory, Academic Press, New York, 1969, 63-69. [48] R. K. Guy, A. Hill, The crossing number of the complement of a circuit, Disc. Math. 5 (1973), 335-344. [49] R. K. Guy, T. A. Jenkyns, The toroidal crossing number of Km>n, J. Combin. Theory 6 (1969), 235-250. BIBLIOGRAPHY 101 [50] R. K. Guy, T. A. Jenkyns, J. Schaer, The toroidal crossing number of the complete graph, J. Combin. Theory 4 (1968), 376-390. [51] F. Harary, P. C. Kainen, A. J. Schwenk, Toroidal graphs with arbitrarily high crossing numbers, Nanta Math. 6 (1973), 58-67. [52] A. Hatcher, Algebraic Topology, Cambridge University Press, New York, 2002. [53] P. Hlineny, Crossing-critical graphs and path-width, in: P. Mutzel, M. J¨unger, S. Leipert, eds., Proc. 9 th Intl. Symposium on Graph Drawing, Lecture Notes in Comput. Sci. 2265, Springer, Berlin, 2001, 102-114. [54] P. Hlineny, Crossing-critical graphs have bounded path-width, J. Combin. Theory Ser. B 88 (2003), 347-367. [55] P. Hlineny, Crossing number is hard for cubic graphs, in: J. Fiala, V. Koubek, J. Kratochv´il, eds., Math Foundations of Computer Science 2004, Lecture Notes in Comput. Sci. 3153, Springer, Berlin, 2004, 772-782. [56] F. Jaeger, Tait’s theorem for graphs with crossing number at most one, Ars Combin. 9 (1980), 283-287. [57] S. Jendrol’, M. ˇčerbova, On the crossing numbers of Sm D Pn and Sm D Cn, Casopis pro pestov´an´i matematiky 107 (1982), 225-230. [58] H. A. Juarez, G. Salazar, Drawings of Cm D Cn with one disjoint family II, J. Combin. Theory Ser. B 82 (2001), 161-165. [59] M. Juvan, B. Mohar, An algorithm for embedding graphs in the torus, submitted. [60] P. C. Kainen, A lower bound for crossing number of graphs with applications to Kn, KPtq, and Q(d), J. Combin. Theory Ser. B 12 (1972), 287-298. [61] P. C. Kainen, On the stable crossing number of cubes, Proc. Amer. Math. Soc. 36 (1972), 55-62. [62] P. C. Kainen, A. T. White, On stable crossing numbers, J. Graph Theory 2 (1978), 181-187. [63] J. W. Kennedy, P. J. Wexler, G. S. Bloom, Linguistic complexity and minimal eodermdromes, Linguistics 18 (1980), 3-16. 102 BIBLIOGRAPHY [64] S. Klavˇzar, B. Mohar, Crossing numbers of Sierpin´ski-like graphs, to appear in J. Graph Theory. [65] D. J. Kleitman, The crossing number of K5n, J. Combin. Theory Ser. B 9 (1971), 315-323. [66] M. Kleˇsˇc, On the crossing numbers of Cartesian products of stars and paths or cycles, Math. Slovaca 41 (1991), 113-120. [67] M. Kleˇsˇc, The crossing numbers of Cartesian products of paths with 5-vertex graphs, Discrete Math. 233 (2001), 353-359. [68] M. Kleˇsˇc, The crossing number of X2)3 D C3, Discrete Math. 251 (2002), 109-117. [69] M. Kleˇsˇc, The crossing number of X2>3 D Pn and X2>3 D Sn, Tatra Mt. Math. Publ. 9 (1996), 51-56. [70] M. Kleˇsˇc, The crossing numbers of products of paths and stars with 4-vertex graphs, J. Graph Theory 18 (1994), 605-614. [71] M. Kleˇsˇc, R. B. Richter, I. Stobert, The crossing number of C5 D Cn, J. Graph Theory 22 (1996), 239-243. [72] M. Kochol, Construction of crossing-critical graphs, Discrete Math. 66 (1987), 311-313. [73] V. R. Kulli, D. G. Akka, L. W. Beineke, On line graphs with crossing number 1, J. Graph Theory 3 (1979), 87-90. [74] K. Kuratowski, Sur le probleme des courbes gauches en topologie, Fund. Math. 15 (1930), 271-283. [75] J. Leanos, G. Salazar, On the additivity of crossing numbers of graphs, preprint. [76] F. T. Leighton, Complexity Issues in VLSI, MIT Press, Cambridge, 1983. [77] F. T. Leighton, New lower bound techniques for VLSI, Math. Systems Theory 17 (1984), 47-70. [78] R. Lipton, R. Tarjan, A separator theorem for planar graphs, SIAM J. Appl. Math. 36 (1979), 177-189. [79] D. Ma, H. Ren, J. Lu, The crossing number of the circular graph C(2m + 2,m), Discrete Math. 304 (2005), 88-93. BIBLIOGRAPHY 103 [80] T. Madej, Bounds for the crossing number of the N-cube, J. Graph Theory 15 (1991), 81–97. [81] D. McQuillan, R. B. Richter, On 3-regular graphs having crossing number at least 2, J. Graph Theory 18 (1994), 831–893. [82] D. McQuillan, R. B. Richter, On the crossing numbers of certain generalized Petersen graphs, Disc. Math. 104 (1992), 311–320. [83] B. Mohar, Obstructions for the disk and cylinder embedding extension problems, Combin. Probab. Comput. 3 (1994), 375–406. [84] B. Mohar, Projective planarity in linear time, J. Algorithms 15 (1993), 482–502. [85] B. Mohar, C. Thomassen, Graphs on Surfaces, Johns Hopkins University Press, Baltimore, 2001. [86] E.G. Moreno, G. Salazar, Bounding the crossing number of a graph in terms of the crossing number of a minor with small maximum degree, J. Graph Theory 36 (2001), 168–173. [87] B. Oporowski, Large four-connected nonplanar graphs, draft. [88] J. Pach, R. Radoiˇci´c, G. Tardos, G. T´oth, Improving the crossing lemma by finding more crossings in sparse graphs, in: J. Snoeyink, J. D. Bois-sonnat, eds., Proceedings of the Twentieth Annual Symposium on Computational Geometry, ACM Press, New York, 2004, 68–75. [89] J. Pach, F. Shahrokhi, M. Szegedy, Applications of the crossing number, Algorithmica 16 (1996), 111–117. [90] J. Pach, J. Spencer, G. T´oth, New Bounds on Crossing Numbers, Discrete Comput. Geom. 24 (2000), 623–644. [91] J. Pach, G. T´oth, Graphs drawn with few crossings per edge, Combina-torica 17 (1997), 427–439. [92] J. Pach, G. T´oth, Which crossing number is it anyway?, J. Combin. Theory Ser. B 80 (2000), 225–246. [93] S. Pan, R. B. Richter, The crossing number of K11 is 100, submitted. 104 BIBLIOGRAPHY [94] M. J. Pelsmajer, M. Schaefer, D. ˇ tefankoviˇc, Odd Crossing Number Is Not Crossing Number, in: P. Healy, N. S. Nikolov, eds., Graph Drawing: 13 th International Symposium, Lecture Notes in Comput. Sci. 3843, Springer, Berlin, 2006, 386-396. [95] B. Pinontoan, R. B. Richter, Crossing numbers of sequences of graphs I: general tiles, Australas. J. Combin. 30 (2004), 197-207. [96] B. Pinontoan, R. B. Richter, Crossing numbers of sequences of graphs II: planar tiles, J. Graph Theory 42 (2003), 332-342. [97] G. Pica, T. Pisanski, A. G. S. Ventre, Cartesian products of graphs and their crossing numbers, in: A. Barlotti, M. Biliotti, A. Cossu, G. Ko-rchmaros, G. Tallini., eds., Combinatorics ’84: Proceedings of the International Conference on Finite Geometries and Combinatorial Structures, Ann. Discrete Math. 30, North-Holland, Amsterdam, 1986, 339-346. [98] R. B. Richter, Cubic graphs with crossing number two, J. Graph Theory 12 (1988), 363-374. [99] R. B. Richter, Subgraphs with crossing number two, Congr. Numer. 60 (1987), 169-180. [100] R. B. Richter, G. Salazar, A survey of good crossing number theorems and questions, preprint. [101] R. B. Richter, G. Salazar, personal communication, 2006. [102] R. B. Richter, G. Salazar, The crossing number of C6 D Cn, Australas. J. Combin. 23 (2001), 135-143. [103] R. B. Richter, G. Salazar, The crossing number of P(N, 3), Graphs Combin. 18 (2002), 381-394. [104] R. B. Richter, J. Siran, The crossing number of K^n in a surface, J. Graph Theory 21 (1996), 51-54. [105] R. B. Richter, C. Thomassen, Minimal graphs with crossing number at least k, J. Combin. Theory Ser. B 58 (1993), 217-224. [106] R. B. Richter, C. Thomassen, Intersections of curve systems and the crossing number of C5 D C5, Discrete Comput. Geom. 13 (1995), 149-159. BIBLIOGRAPHY 105 [107] R. B. Richter, C. Thomassen, Relations between crossing numbers of complete and complete bipartite graphs, Amer. Math. Monthly 104 (1997), 131-197. [108] R. D. Ringeisen, L. W. Beineke, The crossing number of C3 D Cn, J. Combin. Theory Ser. B 24 (1978), 134-136. [109] N. Robertson, P. Seymour, Excluding a graph with one crossing, Con-temp. Math. 147 (1993), 669-675. [110] G. Salazar, Drawings of Cm D Cn with one disjoint family, J. Combin. Theory Ser. B 76 (1999), 129-135. [111] G. Salazar, Infinite families of crossing-critical graphs with given average degree, Discrete Math. 271 (2003), 343-350. [112] G. Salazar, Nearly-light cycles in embedded graphs and in crossing-critical graphs, preprint. [113] G. Salazar, On a crossing number result of Richter and Thomassen, J. Combin. Theory Ser. B 79 (2000), 98-99. [114] G. Salazar, On the crossing numbers of loop networks and generalized Petersen graphs, Discrete Math. 302 (2005), 243-253. [115] E. R. Scheinerman, H. S. Wilf, The rectilinear crossing number of a complete graph and Sylvester’s four point problem of geometric probability, Amer. Math. Monthly 101 (1994), 939-943. [116] F. Sharokhi, O. Sykora, L. A. Szekely, I. Vrto, Crossing numbers: bounds and applications, in: I. B´ar´any, K. Boroczky, eds., Intuitive Geometry, Bolyai Soc. Math. Stud. 6, Springer, Berlin, 1997, 179-206. [117] F. Sharokhi, O. Sykora, L. A. Szekely, I. Vrto, The crossing number of a graph on a compact 2-manifold, Adv. Math. 123 (1996), 105-119. [118] F. Sharokhi, O. Sykora, L. A. Szekely, I. Vrto, Intersection of curves and crossing number of Cm D Cn on surfaces, Discrete Comput. Geom. 19 (1998), 237-247. [119] F. Shahrokhi, L. A. Szekely, On canonical concurrent flows, crossing number and graph expansion, Combin. Probab. Comput. 3 (1994), 523-543. 106 BIBLIOGRAPHY [120] O. Sy´kora, I. Vrˇto, Edge separators for graphs of bounded genus with applications, Theor. Comput. Sci. 112 (1993), 419–429. [121] O. Sy´kora, I. Vrˇto, On crossing numbers of hypercubes and cube connected cycles, BIT 33 (1993), 232–237. [122] O. Sy´kora, I. Vrˇto, On VLSI layouts of the star graph and related networks, Integration, the VLSI Journal 17 (1994), 83–94. [123] J. J. Sylvester, On a special class of questions on the theory of probabilities, Birmingham British Association Report 8 (1865). [124] L. A. Sz´ekely, A successful concept for measuring non-planarity of graphs: the crossing number, Discrete Math. 276 (2004), 331–352. [125] L. A. Sz´ekely, Crossing numbers and hard Erd˝os problems in discrete geometry, Combin. Probab. Comput. 6 (1997), 353–358. [126] E. Szem´eredi, W. T. Trotter, Extremal problems in discrete geometry, Combinatorica 3 (1983), 381–392. ˇ [127] J. Sir´anˇ, Crossing-critical edges and Kuratowski subgraphs of a graph, J. Combin. Theory Ser. B 35 (1983), 83–92. ˇ [128] J. Sir´anˇ, Infinite families of crossing-critical graphs with a given crossing number, Discrete Math. 48 (1984), 129–132. [129] R. Torrens, Ultrasonics: remote control and intruder detector, 4QD-TEC, 2005, http://www.4qdtec.com/ultra.html. [130] P. Tur´an, A note of welcome, J. Graph Theory 1 (1977), 7–9. [131] W. T. Tutte, Toward a theory of crossing numbers, J. Combin. Theory 8 (1970), 45–53. [132] I. Vrˇto, Crossing number of graphs: a bibliography. ftp://ftp.ifi.savba.sk/pub/imrich/crobib.pdf [133] A. T. White, L. W. Beineke, Topological Graph Theory, in: L. W. Beineke, R. J. Wilson, eds., Selected Topics in Graph Theory, Academic Press, New York, 1978, 15–50. [134] D. R. Woodall, Cyclic-order graphs and Zarankiewicz’s crossing-number conjecture, J. Graph Theory 17 (1993), 657–671. BIBLIOGRAPHY 107 [135] Y. Yuansheng, L. Xiaohui, L. Jianguo, H. Xin, The crossing number of C(n, {1, 3}), Discrete Math. 289 (2004), 107–118. [136] Y. Yuansheng, L. Xiaohui, L. Jianguo, H. Xin, The crossing number of C(mk,{1, k}), Graphs Combin. 21 (2005), 89–96. [137] K. Zarankiewicz, On a problem of P. Tur´an concerning graphs, Fund. Math. 41 (1954), 137–145. 108 BIBLIOGRAPHY Index of Terms active vertex, 35 adjacent edges, 5 faces, 9 vertices, 5 aligned family, 44, 58 pair, 44 annihilating a crosscap, 86 apex, 40, 65 area, 23 augmented embedding, 89 graph, 87, 89 average degree, 22, 26, 56, 60, 63 axis, 51 binary tree, 23 bisection width, 18 block, 6, 7, 83 bridge gadget, 52 bundle, 32, 50, 69 coherent, 32–35, 38 splitting of, 32–34, 50, 51 cap, 65 Cartesian product, 7, 20, 68, 96 capped, 65, 66 chromatic index, 7, 59 number, 7 circuit, 23, 27 clone, 50 coherent bundles, 32–35, 38 clone gadgets, 50 gadgets, 43 pairs, 44 sets, 44 coloring, 7, 59 compatible sequence, 39 tiles, 39 complement of a graph, 7 of a tile, 41 complete bipartite graph, 8, 59, 93 graph, 7, 91 component, 6 congestion, 17 connected, 23, 83 graph, 6 tile, 41 vertices, 6 contracted edge, 8, 76, 79, 80 cover, vertex, 6, 37 critical sequence, 43, 45, 55, 57 crosscap, 9, 82 crossed fence, 23 crossing, 10 edge-edge, 77 edge-vertex, 77 vertex-vertex, 77 Crossing Lemma, 15, 16, 24 109 110 INDEX OF TERMS crossing number, 10 major, 76 minor, 27, 76 odd, 15 pair, 15 rectilinear, 11, 25 tile, 39 crossing-critical edge, 21 graph, 10, 21, 35, 43, 60 cubic graph, 5, 59, 77 cut, 40, 42, 45 cutedge, 6 cutvertex, 6 cycle, 67, 96 cyclically-compatible sequence, 39, 42 tile, 39 cyclization, 40, 42, 45, 55, 57 decomposition of a crossing-critical graph, 23, 38 of a surface, 83 degenerate drawing, 86, 87 tile, 43, 55, 57 degree average, 22, 26, 56, 60, 63 maximum, 5, 79, 81 minimum, 5, 22 of a clone gadget, 50 of a vertex, 5 digon, 89 disjoint union, 7 distance, 24 distant edge, 32 dominating vertex, 6, 65, 66 drawing, 10 degenerate, 86, 87 graph of, 10, 89 normal, 10 optimum, 10 realizing, 76, 82 rectilinear, 10 tile, 39 edge, 5 congestion, 17 contracted, 8, 76, 79, 80 crossing-critical, 21 distant, 32 near, 32 original, 8, 76 removed, 8, 76 rotation, 9, 31 unbalanced, 65 edge-coloring, 7, 59 edge-connected graph, 6, 23 embedding augmented, 89 into a graph, 17 into a surface, 9, 87 method, 17 empty graph, 8, 65 endvertex, 5 eodermdrome, 25 equivalent sequences, 40 Euler characteristic, 9 Formula, 9, 82, 89, 90 genus, 9, 10, 87, 89 extending family, 45 of a pair, 45 face infinite, 10 of a drawing, 10 of an embedding, 9 facial walk, 9 family INDEX OF TERMS 111 aligned, 44, 58 extending, 45 infinite, 60 propagating, 45, 57 saturating, 45 twisted, 44, 57 fence, crossed, 23 flip, 40 forbidden minor, 8, 85 forest, 6 function, zip, 31 gadget, 43 bridge, 52 clone, 50 coherent, 43 wheel, 51, 69 genus, 82 Euler, 9, 10, 87 of a graph, 9 of a surface, 9 girth, 6, 82 graph, 5 augmented, 87, 89 complete, 7, 91 bipartite, 8, 59, 93 crossing-critical, 10, 21, 35, 43, 60 cubic, 5, 59, 77 edge-connected, 6, 23 empty, 8, 65 homeomorphic, 7 isomorphic, 6 line, 7, 14 of a drawing, 10, 89 Petersen, 59, 85 realizing, 27, 76, 77 regular, 5, 22, 63 simple, 5 subcubic, 5 handle, 9, 82 homeomorphic graph, 7 homogeneous neighborhood, 35 homomorphism, 6 hub, 51 hypercube, 8, 19, 94 incidence, 24 incident edge and face, 9 vertex and edge, 5 vertex and face, 9 index, chromatic, 7, 59 induced subgraph, 6 infinite face, 10 family, 60 point, 10 internal vertex, 32, 51 intersection, 7 intertwined pair, 52 inverted tile, 40, 56 isomorphic graph, 6 isomorphism, 6 join of a sequence, 40 of graphs, 7 of tiles, 40 Klein bottle, 9, 88 left in a tile, 45 inverted tile, 40 wall, 39 length, 6 line, 24 graph, 7, 14 loop, 5 major crossing number, 76 maximum degree, 5, 79, 81 112 minimum degree, 5, 22 minor, 8, 79, 81 crossing number, 27, 76 forbidden, 8, 85 minor-closed property, 8, 76 multigraph, 5 multiplicity neighborhood, 5, 31 near edge, 32 neighbor, 5 neighborhood, 5 homogeneous, 35 multiplicity, 5, 31 nonorientable surface, 9 normal drawing, 10 number chromatic, 7 crossing, 10 odd crossing number, 15 optimum drawing, 10 orientable surface, 9 orientably degenerate drawing, 86 orienting system, 86 original edge, 8, 76 pair aligned, 44 coherent, 44 crossing number, 15 intertwined, 52 split, 52 twisted, 44, 57 path, 6, 66, 69, 70 traversing, 44, 45 path-width, 23 perfect tile, 41, 42 Petersen graph, 59, 85 planar tile, 41 point, 24 infinite, 10 random, 25 INDEX OF TERMS product capped Cartesian, 65, 66 Cartesian, 7, 20, 68, 96 zip, 26, 31, 59, 60, 65 projective plane, 9, 85 propagating family, 45, 57 property, minor-closed, 8, 76 realizing drawing, 76, 82 graph, 27, 76, 77 rectilinear crossing number, 11, 25 drawing, 10 regular graph, 5, 22, 63 removed edge, 8, 76 reversed sequence, 40 tile, 40 right in a tile, 45 inverted tile, 40 wall, 39 rim, 51 rotation of edges, 9, 31 of vertices, 9, 65 saturating family, 45 semiactive vertex, 35 separator, 6 sequence compatible, 39 critical, 43, 45, 55, 57 cyclically-compatible, 39, 42 equivalent, 40 reversed, 40 staircase, 55 shift, 40 simple graph, 5 sink, 32, 51 INDEX OF TERMS 113 source, 32, 51 spanned subgraph, 6 spanning subgraph, 6 sphere, 9, 83 split pair, 52 splitting a bundle, 32–34, 50, 51 spoke, 51, 69 staircase sequence, 55 strip, 26, 46, 47, 55 tile, 55 star, 8, 68 subcubic graph, 5 subdivision, 7, 69 subgraph, 6 induced, 6 spanned, 6 spanning, 6 surface, 9 nonorientable, 9 orientable, 9 suspension, 65, 67 of a graph, 65 of a tile, 40 system, 86 tile, 26, 39 compatilbe, 39 connected, 41 crossing number, 39 cyclically-compatible, 39 degenerate, 43, 55, 57 drawing, 39 in a graph, 41 inverted, 40, 56 perfect, 41, 42 planar, 41 reversed, 40 staircase, 55 torus, 9 touching, 10 transformation, Y ?, ?Y , 7, 85 traversing path, 44, 45 tree, 6, 65, 68, 72 binary, 23 tree-width, 23 triangle, 7 tripod, 52 twist, 40 twisted family, 44, 57 pair, 44, 57 staircase strip, 46, 55 unbalanced edge, 65 union, disjoint, 7 vertex, 5 active, 35 congestion, 17 cover, 6, 37 dominating, 6, 65, 66 internal, 32, 51 rotation, 9, 65 semiactive, 35 VLSI, 15, 23, 26 walk, facial, 9 wall, 39 weight, 80 wheel, 8, 69 gadget, 51, 69 in a graph, 51 width bisection, 18 path-, 23 tree-, 23 zip function, 31 product, 26, 31, 59, 60, 65 114 INDEX OF TERMS Index of Symbols Di Qa D2, 31 Qd, 8 E(B), 32 S„, 8 E(G), 5 Tv, 8, 77 E(v,v'), 50 F(G), 5 F(k), 85 Wn, 8 F(fc,E), 85 degG(v), 5 G, 76 eg(G), 10 G-e, 6 eg(E), 9 G-v, 6 5(G), 9 G[F], 6 g{G), 9 G[U], 6 ¦č(u), 65 G<#, 6 mcr(G), 76 G 8 L(G), 7 Mcr(G,E), 76 iVG(u), 5 ng(v)> 5 Pm, 6 X(G), 7 X'(G), 7 X(ß), 9 Xl(v), 65 w(fc), 85 w(fc,E), 76, 85 Pu, 6 115 116 INDEX OF SYMBOLS Razširjeni povzetek Definicije V tem razdelku predstavimo osnovne pojme teorije prekrižnega števila. Pri tem predpostavimo, da je bralec seznanjen s terminologijo teorije grafov in topologije. Viri za seznanjanje s temi temami so [27, 38, 52]. Z izrazom graf označimo multigraf brez zank. Zanke namreč pri študiju prekrižnega števila niso pomembne, saj lahko v vsako risbo grafa dodamo poljubno mnogo zank, ne da bi povečali število križišč. Kadar želimo poudariti, da graf nima večkratnih povezav, uporabimo izraz enostaven graf. Od standardne terminologije nekoliko odstopa le pojem okolice vozlišča v grafu. Z NG(v) označimo običajno okolico vozlišča v v grafu G, t. j. množico vseh sosedov v. Z iV* (v) pa označimo multiokolico vozlišča t;, t. j. multimnožico, v kateri se vsak sosed vozlišča v pojavi tolikokrat, kot je večkratnost njegove povezave z v. Risba grafa G na ploskvi S je par preslikav D = ( k in cr(H, E) < k za vsak pravi podgraf H grafa G. Graf je prekrižno-kritičen za E, če je k-prekrižno-kritičen za E za neki k. Kadar omembo ploskve izpustimo, predpostavimo kritičnost za ravnino (sfero). Premočrtna risba enostavnega grafa je risba na ravnini E2, na kateri je risba e(e, [0,1]) vsake povezave e G E{G) daljica. Premočrtno prekrižno število rcr(G) je najmanjše število križišč na premočrtni risbi grafa G. Prispevek disertacije k teoriji prekrižnega števila Rezultati disertacije razširjajo teorijo prekrižnega števila v treh smereh: z novo konstrukcijo prekrižno-kritičnih grafov pokažemo na strukturo, ki jo lahko imajo tovrstni grafi, pokažemo več rezultatov o prekrižnih številih kartezičnih produktov grafov, poleg tega pa uvedemo minorsko monotono različico prekrižnega števila grafov. Prekrižno-kritični grafi so minimalni s predpisanim prekrižnim številom, zato njihove lastnosti omogočajo vpogled v strukturno obnašanje te grafovske invariante. Uvedel jih je Širan, ki je za vsak k > 3 konstruiral neskončno družino fc-prekrižno-kritičnih grafov [127]. Kochol je za vsak k > 2 konstru- Razširjeni povzetek 119 iral neskončno družino enostavnih fc-prekrižno kritičnih grafov [72]. Richter in Thomassen sta začela opazovati stopnje vozlišč v enostavnih prekrižno-kritičnih grafih [105]. Najprej sta pokazala, da je prekrižno število takega grafa G omejeno z linearno funkcijo parametra k, cr(G) < § k + 16, iz česar sledi, da za vsak k > 1 in r > 6 obstaja le končno mnogo enostavnih k-prekrižno-kritičnih grafov z minimalno stopnjo r. Salazar je argument razširil na povprečno stopnjo: za vsak racionalen r > 6 obstaja le končno mnogo enostavnih fc-prekrižno-kritičnih grafov s povprečno stopnjo r [111]. Konstruiral je neskončno družino enostavnih fc-prekrižno-kritičnih grafov s povprečno stopnjo r za vsak racionalen r G [4, 6) ter za neskončno različnih k in zastavil naslednje vprašanje: Vprašanje 1 ([111]). Naj bo r racionalno število z intervala (3,4). Ali obstaja celo število k in neskončna družina (enostavnih) 3-povezanih grafov s povprečno stopnjo r, ki so vsi k-prekrižno-kritični? Na vprašanje 1 sta deloma pozitivno odgovorila Pinontoan in Richter, ki sta iskane družine konstruirala za r G (3±, 4) [96]. Za ta namen sta razvila teorijo tlakovcev, ki jo bomo uporabili tudi v pričujočem delu. V nadaljevanju uvedemo novo grafovsko operacijo, šiv, s pomočjo katere lahko kombiniramo dva grafa ali dve risbi. Ob ustrezni povezanosti grafa pri vozliščih, ki so vpletena v šivanje, ta operacija ohranja prekrižno število grafov, ob zadostni simetriji v soseščini teh vozlišč pa ohranja tudi kritičnost grafov. Operacijo šivanja uporabimo skupaj z razširitvijo teorije tlakovcev Pi-nontoana in Richterja [96], ki omogoči posplošitev prekrižno-kritičnih grafov Kochola [72]. Tako izdelamo sedemparametrično družino prekrižno-kritičnih grafov, s pomočjo katere pokažemo osnovni rezultat tega dela: natančen izbor parametrov omogoča, da konstruiranim grafom predpišemo ne le poljubno racionalno povprečno stopnjo r G (3,6), ampak tudi poljubno dovolj veliko prekrižno število, s čimer v polnosti odgovorimo na Salazarjevo vprašanje in v enem izreku zaobjamemo prej omenjene rezultate o obstoju neskončnih družin fc-prekrižno-kritičnih grafov. Poudarek na raziskovanju prekrižno-kritičnih grafov je bil na 3-(povezav-no)-povezanih grafih. Ta pogoj onemogoči vozlišča stopnje dve, ki so trivialna za prekrižno število. Vendar je pogoj mnogo močnejši in šele pred kratkim sta ga upravičila Leanos in Salazar, ko sta našla dekompozicijo 2-povezanih prekrižno-kritičnih grafov v 3-povezane komponente [75]. S pomočjo šivanja prekrižno-kritičnih grafov pokažemo, da podobna dekompozicija ne obstaja za fc-povezane prekrižno kritične grafe, k > 3. Zaradi obilice simetrije so kartezični produkti grafov pritegnili precej pozornosti pri določanju prekrižnih števil. Beineke in Ringeisen sta določila prekrižno število grafov G D Cn za vse grafe G reda štiri, razen za K1>3 [12]. 120 Razširjeni povzetek i g? r (a) (b) M 11; r W ^M (c) Slika 1: Minorsko prekrižno število in križišča v elektronskih vezjih. To vrzel sta zapolnila JendroP in Sčerbova, ki sta poiskala prekrižno število S3nCn, S3n Pm in S4 D P2 ter postavila naslednjo domnevo: Domneva 2 ([57]). cr(Sra D Pm) = (m - 1) [f J [^\ za n > 3, m > 1. Klešč je domnevo pokazal za n = 4 in m > Iv [66], kjer je določil tudi cr(S4 D Cm) za m > 3. V [70] je določil prekrižno število GDPminGD5n za vsak graf G reda štiri in v [67] prekrižno število G D Pm za vsak graf reda G pet. Za več grafov reda pet je znano tudi prekrižno število njihovega kartezičnega produkta s Cn ali Sn, poleg tega pa še več drugih kartezičnih produktov [66, 71, 67, 69, 68], največ jih je pokazal Klešč. Kartezične produkte grafov z drevesi lahko iterativno sestavimo s pomočjo šivanja. Če pri tem zahtevamo spoštovanje pogoja povezanosti, ki zagotavlja ohranjanje prekrižnega števila, nam kot motnja preostanejo le odvečna vozlišča, ki ustrezajo listom drevesa. V nekaterih primerih lahko z dodatno operacijo taka vozlišča dopolnimo do pravega kartezičnega produkta. Tako pokažemo več rezultatov o prekrižnih številih kartezičnih produktov, med drugim o kartezičnem produktu zvezd K1>n in koles Wn z drevesi. V posebnem razrešimo domnevo JendroPa in Ščerbove za vsak n,m>l. Prekrižno število ima več uporab pri izdelavi integriranih vezij [13, 23, 76, 77, 122]. Pri tem je cilj poiskati ravninsko risbo grafa danega elektronskega vezja, ki ima najmanjše število križišč. Na ta način pa ne izkoristimo lastnosti elektronskega vezja, da imajo točke, povezane z navadnimi žicami, enak električni potencial. Zato lahko ustrezne povezave stisnemo in razširimo na drugačen način. S tem dobimo ekvivalentno elektronsko vezje, katerega graf pa ima lahko manjše prekrižno število. Ta pristop ilustriramo na sliki 1: (a) prikazuje originalno shemo visokofrekvenčnega oddajnika [129], (b) prikazuje ekvivalentno shemo, v kateri so točke z enakim potencialom stisnjene v eno vozlišče, (c) pa prikazuje shemo, ki je ekvivalentna prejšnjima dvema in ima eno križišče manj kot (a). Razširjeni povzetek 121 Minorsko prekrižno število, ki ga uvedemo v nadaljevanju, je naraven model za ta problem. Z njim iščemo najmanjše število križišč v taki risbi grafa, v kateri smo vozlišča nadomestili z drevesi in se povezave teh dreves lahko sekajo. Taka zamenjava v elektronskem vezju ustreza raztegnitvi točke z enakim potencialom v več žic. Tako dobljen realizirajoči graf vsebuje originalni graf G kot minor in ta različica prekrižnega števila je minorsko monotona. S tem razrešimo problem, ki ga je odprl Seymour, ko je obžaloval, da prekrižno število ne sodeluje s teorijo grafovskih minorjev: odstranitev povezave prekrižnega števila nikoli ne poveča, stiskanje povezave pa ga lahko spremeni v obe smeri [7]- V delu pokažemo več splošnih spodnjih mej za to grafovsko invarianto, raziščemo strukturo grafov z omejenim minorskim prekrižnim številom in znanje o njej uporabimo za izboljšavo spodnjih mej. Ena od spodnjih mej je posplošitev rezultata Morene in Salazarja, ki sta podoben rezultat pokazala za grafe z maksimalno stopnjo štiri v [86]. Meje uporabimo na polnih grafih, polnih dvodelnih grafih, hiperkockah in na produktih dveh ciklov. Poleg tega pokažemo eksaktne vrednosti za male polne grafe Kn, 1 < n < 8, ter za polne dvodelne grafe K^n in KA>n, n > 1. Prekrižno-kritični grafi Šiv grafov in risb Za i = 1,2 naj bo d graf in Vi G V (d) njegovo vozlišče stopnje d. Naj bo Ni = N*G.{vi) multiokolica Vi in o : Nx -»¦ N2 bijekcija. Funkcijo o imenujemo igla grafov d in G2 pri vozliščih vx in v2. Šiv grafov d in G2 z iglo a je graf d QaG2, ki ga dobimo iz disjunktne unije grafov Gl-vl in G2-v2, ko dodamo povezavo ua{u) za vsak u G Nx. Z oznako d V1QV2 G2 opišemo množico paroma neizomorfnih grafov, ki jih dobimo kot šiv d QaG2 za neko iglo o : Nx -»¦ N2. Naj bo Di risba grafa G*. Ta določa rotacijo vozlišč iz iV* okrog vozlišča v^ Vozlišča Ni usklajeno z rotacijo vozlišč označimo z bijekcijo m : iV* -»¦ {l,...,d}. Funkcija a : Nx -»¦ N2, a = vr^V, je igla risb Dx in D2 pri vozliščih vi in v2. Šiv risb Dx in D2 z iglo o je risba Dx ®a D2, ki jo dobimo iz Dx z vložitvijo zrcalne slike risbe D2, ki ima v2 na neskončnem licu, disjunktno v neko lice Du ki vsebuje vu z odstranitvijo vozlišč vx in v2 skupaj z njunima majhnima diskastima okolicama ter s spojitvijo povezav okrog vx in v2 v skladu z iglo a, prim. sliko 2. Ker o odraža zaporedje vozlišč okrog vx in v2, je povezave med Dx in D2 mogoče spojiti brez dodatnih križišč. Šiv risb Dx Qa D2 je risba grafa Gx Qa G2, torej velja naslednja lema: 122 Razširjeni povzetek Slika 2: Šiv risb Dx in D2. Lema 3. Za i = 1,2 naj bo A optimalna risba grafa Gi} Vi G V (G i) vozlišče stopnje d in o igla risb Dx in D2 pri vx in v2. Potem je cr(Gi Qa G2) < cr(G1) + cr(G2). Kadar igla ne spoštuje rotacije vozlišč v optimalni risbi, je mogoče pokazati nekoliko šibkejšo zgornjo mejo: Lema 4. Kadar je G G Glvi&V2 G2 ter je za % = 1,2 vozlišče Vi G V (G i) stopnje d, velja cr(G) < cr(Gi) + cr(G2) + (d~l). Naj bo v G V {G) vozlišče stopnje d v G. Butara B pri v je množica d povezavno disjunktnih poti od v do nekega vozlišča u G V {G), u ^ v. Vozlišče v je začetek butare in u njen konec. Ostala vozlišča na poteh v B so notranja vozlišča butare. Za butaro B pri vozlišču t; G V(G) naj L(S) = E(B)DE(G-v) predstavlja množico povezav na poteh v B, ki niso sosednja z v. Imenujemo jih oddaljene povezave butare B. Dve butari Bx in S2 pri t; sta usklajeni, če imata disjunktni množici oddaljenih povezav. Povezave butare B, ki niso oddaljene, so bližnje povezave. Kadar šivamo grafe pri vozliščih, ki imajo butaro, prekrižno število novega grafa ne pade pod prekrižno število originalnega. To sledi iz naslednje lerne, ki jo pokažemo s pomočjo razcepitve poti butare pri njenih notranjih vozliščih v risbi šiva. Nova risba vsebuje podrisbo subdivizije originalnega grafa. Ker nismo pridobili novih križišč, trditev velja. Lema 5. Za i = 1,2 naj bo G* graf, Vi G V (d), deg(^) = d, Nt = N*Gi(Vi). Privzemimo, da obstaja butara B pri v2 v G2 in naj bo D risba G = Gx ©„ G2. Za poljubno iglo o : Nx -»¦ N2 je v D na povezavah iz E(GX - vx) U E{B) vsaj cr(Gi) križišč. Dl Qa D2 Razširjeni povzetek 123 Lemo 5 skupaj z ustrezno delitvijo križišč med štirimi (skoraj) subdivizijami grafov d in G2 v šivu uporabimo v dokazu naslednje spodnje meje, ki je ključna pri uporabi šivanja za dokazovanje prekrižnega števila grafov: Lema 6. Za i =1,2 naj bo G i graf in Vi G V {G i) njegovo vozlišče stopnje d, Ni = ngM) ter naJ Pn Vi obstajata dve usklajeni butari BiA in Bi>2 v G*. Potem velja cr(Gi ©«, G2) > cr(Gi) + cr(G2) za poljubno iglo o : Nx U N2. Kadar je eden od grafov ravninski, namesto navedenih štirih zadošča zgolj ena butara pri vozlišču iz ravninskega grafa. Šivanje večkrat uporabljamo iterativno. Za take primere pokažemo, da ob ustreznih pogojih ohranja (povezavno) povezanost grafov in število paroma usklajenih butar pri vozliščih šivanih grafov. Poleg vrednosti prekrižnega števila lahko šivanje ohranja tudi kritičnost grafov. Pogoj, ki mu morata grafa zadoščati, je zadostna simetričnost sosedov šivanih vozlišč. Naj bo S C V {G) množica vozlišč G in T C Aut(G) podgrupa grupe avtomorfizmov grafa. Pravimo, da je S T-homogena v G, če za vsako permutacijo vr elementov S obstaja avtomorfizem a G T, za katerega je a/S = iT. ZaSC V (G) naj T(S) predstavlja stabilizator množice S v Aut(G) po točkah. Vozlišče v G V {G) ima homogeno okolico v G, če je NG(v) T({v})-homogena v G. Zadosten pogoj za homogenost okolice v enostavnem grafu je, da imajo vsi sosedi isto množico sosedov. Tako so polni in polni dvodelni grafi primer grafov, v katerih ima vsako vozlišče homogeno okolico. Vozlišče v grafa G je polaktivno, če pri njem obstajata dve usklajeni butari v G. Če ima v poleg tega tudi homogeno okolico v G in nima sosednjih večkratnih povezav, potem je v aktivno vozlišče. S (G) in A(G) zaporedoma označujeta množici polaktivnih in aktivnih vozlišč G. Naslednji izrek omogoča izdelavo novih prekrižno-kritičnih grafov s šivanjem manjših prekrižno-kritičnih grafov. Dokažemo ga s šivanjem optimalnih risb teh manjših grafov, pri čemer simetrija v vozliščih zagotavlja, da je šiv mogoče brez uvedbe novih križišč izvesti tudi z optimalnimi risbami grafov, ki smo jim odstranili povezavo. Izrek 7. Za i = 1,2 naj bo G; graf z vozliščem Vi G G; stopnje d. Če je Vi G S (d) in v2 G A(G2), potem za vsak graf G G Gx VlQV2 G2 velja: (i) cr(G)=cr(G1) + cr(G2). Ob dodatni predpostavki vx G A{GX) velja: (ii) Če je za j = 1, 2 graf G j krprekrižno-kritičen, potem je G k-prekrižno-kritičen za k = maxJ(cr(GJ) + k3_,). 124 Razširjeni povzetek (iii) Če za j G {1,2} velja v G S(G3), v ^ v3 in je NGj(v) TGj({v,v3})-homogena, potem v G A(G). Pri dokazu izreka 7 ne uporabimo dejstva, da lahko risbo pred šivanjem zrcalimo. Edina zanimiva razširitev izreka z uporabo zrcaljenja je pri vozliščih stopnje tri, ko lahko s pomočjo zrcaljenja in cikličnih rotacij dosežemo vse možne permutacije povezav v šivu. V tem primeru pri (i) in (ii) ni treba zahtevati pogoja homogenosti okolice, trditev (iii) pa ne velja. To posebnost vozlišč stopnje tri lahko izkoristimo tudi za izdelavo prekrižno-kritičnih grafov iz manjših, nekritičnih grafov. Kadar imajo slednji vozliščno pokritje iz polaktivnih vozlišč stopnje tri, lahko na vsako od vozlišč pokritja prišijemo prekrižno-kritičen graf, ki zagotovi kritičnost povezav, sosednjih z vozliščem šivanja. Leanos in Salazar sta našla dekompozicijo 2-povezavno-povezanih prekrižno-kritičnih grafov na manjše 3-povezavno-povezane prekrižno-kritične grafe [75]. Zgornja konstrukcija pove, da za 3-povezavno-povezane prekrižno-kritične grafe podobna dekompozicija ne obstaja, saj obstajajo grafi z ustreznim vo-zliščnim pokritjem, ki niso prekrižno-kritični. Tlakovci Naj bo G graf in A = (A0,..., \i), p = (p0, • • •, Pr) dve disjunktni zaporedji vozlišč v G, v katerih vsako vozlišče G nastopa kvečjemu enkrat. Urejeni trojki T = (G, A, p) pravimo tlakovec. Risbi G na enotskem kvadratu [0,1] x [0,1], na katerega robovih ležijo natanko vozlišča leve stene A na {0} x [0,1] in desne stene p na {1} x [0,1], rečemo tlakovska risba T, če je zaporedje padajočih y-koordinat vozlišč v A in p usklajeno z zaporedjema A in p. Tlakovsko prekrižno število tcr(T) tlakovca T je najmanjše število križišč na kaki tlakovski risbi T. Tlakovec T = (G, A, p) je združljiv s tlakovcem T' = (G', A', p'), če velja \p\ = |A'|. Tlakovec T je krožno združljiv, če je združljiv sam s seboj. Zaporedje tlakovcev T = (T0,... ,Tm) je združljivo, če je T; združljiv s Ti+1 za i = 0,... ,m - 1. Zaporedje je krožno združljivo, če je združljivo in je Tm združljiv s T0. Za vsa zaporedja tlakovcev privzamemo, da so združljiva. Spoj dveh združljivih tlakovcev T in T' je definiran kot T ® T' = (G ® G', A, p'), kjer je G ® G' graf, ki ga dobimo iz disjunktne unije grafov G in G' po identifikaciji p* z A^ za i = 0,..., \p\ - 1. Ker je operacija asociativna, lahko definiramo spoj združljivega zaporedja T = (T0,...,Tm) kot tlakovec ®T = T0 0 Ti ® ... ® Tm. Spoj dveh tlakovcev lahko vsebuje dvojne povezave ali vozlišča stopnje dve. Dvojne povezave obdržimo, vozlišča stopnje dve pa odstranimo s stiskanjem ene od sosednjih povezav. Razširjeni povzetek 125 Za krožno združljiv tlakovec T = (G, A, p) definiramo njegov krožni spoj oT kot graf, ki ga dobimo iz G po identifikaciji A* z Pi za i = 0,..., \p\ - 1. Podobno definiramo krožni spoj krožno združljivega zaporedja tlakovcev kot oT = o(®T). Ker lahko tlakovske risbe združljivih tlakovcev spajamo brez uvedbe novih križišč, velja naslednja lema: Lema 8 ([96]). Za krožno združljiv tlakovec T velja cr(oT) < ter (T). Za združljivo zaporedje tlakovcev T = (T0,..., Tm) velja tcr(®T) < L™0 ter (T*). Za zaporedje u naj ü predstavlja obratno zaporedje. Naj bo T = (G, A, p) tlakovec. Njegov desno-zviti tlakovec T* je (G, A, p), njegov levo-zviti tlakovec iT je (G, A, p), njegov zviti tlakovec je iT* = (G, A, p). Obrnjeni tlakovec tlakovca T je T" = (G, p, A). Naj bo T = (T0,...,Tm) zaporedje tlakovcev. Obrat zaporedja T je r" = (Tm , • • •, T(T)- Zlitje zaporedja T je T* = (T0,..., Tm_x,Tl). Za i = 0,..., m je zaporedje T* = (T0,..., Ti_i, t/, lTi+1, Ti+2,..., Tm) z-sioi zaporedja T. Zaporedje T/i = (Ti+1,..., Tm, T0,..., T^) je «-rez zaporedja T. Zaporedje % = (Ti}..., Tm, T0,..., Ti+1) je i-prevoj zaporedja T. Pri zadnjih dveh operacijah predpostavljamo krožno združljivost zaporedja T. Dve zaporedji tlakovcev T in T iste dolžine sta ekvivalentni, če lahko dobimo eno iz drugega z zaporedjem prevojev, skokov in obratov. Grafa, ki ju dobimo s krožnim spojem takih zaporedij, sta enaka. Tlakovec T = (G, A, p) je ravninski, če velja tcr(T) = 0, in je povezan, če je G povezan. Je popoln, če velja (i) |A| = |p|, (ii) grafa G - A in G - p sta povezana, (iii) za vsak v G A (in v G p) v G obstaja pot do p (oz. A), notranje disjunktna z A (oz. p) in (iv) za vsak 0 < i < j < |A| obstaja par disjunktnih poti P^ in P^ v G, tako da P^ povezuje A* z p; in P^ povezuje A,- z p,-. Naj bo T = (G, A, p) tlakovec in H graf, ki vsebuje G kot podgraf. Komplementarni tlakovec za T v H je tlakovec #-T = (#[(V(#)\V(G))UAUp]-E{G),p,X). Obravnavamo ga lahko kot komplement G v H, iz katerega smo odstranili vsa vozlišča T razen njegovih sten. Če velja o(T® {H-T)) = H, t. j. vozlišča AUp ločijo G od H- G, pravimo, da je T tlakovec v H. Z uporabo tega koncepta naslednja lema pokaže bistveno lastnost popolnih tlakovcev. Izrek, ki sledi lemi, to lastnost uporabi za spodnjo mejo prekrižnega števila grafov, ki jih dobimo s krožnim spojem zaporedij tlakovcev, njegova posledica pa za natančno določitev prekrižnega števila. Splošnejšo obliko izreka potrebujemo v nadaljevanju za dokaz kritičnosti v konstrukciji prekrižno-kritičnih grafov iz zaporedij tlakovcev. Lema 9. Naj bo T = (G, A, p) popoln ravninski tlakovec v H, za katerega obstajata disjunktna podgrafa Gx in Gp v H, vsebovana v isti komponenti 126 Razširjeni povzetek H -T, za katera velja G D Gx = (A, 0), G D Gp = (p, 0). Cev neki risbi D grafa H na povezavah množice E(G) in vsaj še ene od E(GX) ali E{GP) ni križišč, potem sta D-inducirani risbi T in H - T homeomorfni tlakovskima risbama. Izrek 10. Naj bo T = (To,...,Th...,Tm) krožno združljivo zaporedje tlakov-cev. Če velja m>^k-2in za vsak % = 0,... ,m, % ^ l, velja tcr(®(T/i)) > k ter je Ti popoln ravninski tlakovec, potem velja cr(oT) > k. Posledica 11. Naj bo T = (T0,...,Ti,...,Tm) krožno združljivo zaporedje tlakovcev in k = min^ ter (® (T/i)). Če je m > ik - 2 in je Ti popoln ravninski tlakovec za vsak i = 0,... ,m, i ^ l, potem je cr(oT) = k. Tlakovec T je k-izrojen, če je popoln, ravninski in za vsako povezavo e G E(T) velja tcr(Tl-e) < k. Zaporedje tlakovcev T = (T0,..., Tm) je k-kritično, če je tlakovec T* fc-izrojen za vsak i = 0,... ,m in je minMmtcr(®(Tl/i)) > k. Naslednjo splošno konstrukcijo fc-prekrižno-kritičnih grafov pokažemo s pomočjo fc-kritičnih zaporedij tlakovcev in izreka 10. Posledica 12. Naj bo T = (T0,... ,Tm) k-kritično zaporedje tlakovcev. Potem je T = ®T k-izrojen tlakovec. Če je potem je o (T*) k-prekrižno-kritičen graf. tem je T = ®T k-izrojen tlakovec. Če jem>4k-2 in je T krožno združljivo, Th Z izrekom 10 in posledicama 11 ter 12 smo ugotavljanje prekrižnega števila grafa in njegove kritičnosti prevedli na ugotavljanje tlakovskega prekrižnega števila. V nadaljevanju razvijemo ovire, s pomočjo katerih si pri slednjem lahko pomagamo. V splošnem je v danem tlakovcu lahko prisotnih več ovir. Če so te konsistentne, potem so križišča, ki jih povzročijo v tlakovski risbi, različna. Primer konsistentnih ovir so povezavno disjunktne ovire, pojem konsistentnosti pa lahko opredelimo širše s pomočjo teorije množic. Zviti par {P,Q} v tlakovcu T = (G,X,p) je ovira, sestavljena iz dveh prekrižanih prečnih poti, t. j. disjunktnih poti od A do p, katerih začetka z indeksoma %(P), %(Q), si v A sledita v obratnem vrstnem redu kot njuna konca z indeksoma j (P), j(Q) v p. V vsaki tlakovski risbi T mora biti vsaj eno križišče povezave prve poti iz zvitega para s povezavo druge poti. Konsistentni družini zvitih parov rečemo zvita družina. Moč vsake zvite družine v tlakovcu je spodnja meja za njegovo tlakovsko prekrižno število. Par prečnih poti, ki ni zvit, je poravnan, poravnana družina pa je konsistentna družina poravnanih parov. Naj bo tlakovec T združljiv s tlakov-cem T' in naj bo {P, Q} zvit par v T. Poravnan par {P', Q'} v T' razširja {P,Q} na desno, če velja j (P) = i(P'), j(Q) = i(Q'). V tem primeru je {PP', QQ'} zvit par v spoju T ® T'. Desno-razširjajoča družina T' zvite Razširjeni povzetek 127 U = U\ = u\ = U2 = Vi Us = u'3 u2 v'i v2 S2 s' s" —: un V = u'n = V,n_l = Vn = v'n «5 u'5 Vn-1 Slika 3: Stopničasti tlakovec. stopničastega traku. Prekinjene povezave so del tlakovca, a ne del družine T v T je poravnana družina T' v V, za katero obstaja taka bijekcija e : T -»¦ T1, da par e({P, Q}) G J7' razširja par {P, Q} na desni. V tem primeru je T®eT' = {{PP', QQ'} | {P', Q'} = e{{P, Q})} zvita družina v T®T'. Podobno definiramo razširjanje na levo. Naj bo T = (T0,..., Th ..., Tm) združljivo zaporedje tlakovcev in Ti zvita družina vT,. Če za i = l + 1,..., m (oz. i = l - 1,..., 0) obstaja poravnana družina T za J=i ® ... ® J^_i (oz. Fi+1 ® ... ® ^_i), ki razširja slednjo v desno (oz. levo), potem se J=i v zaporedju T razteza v desno (levo). J=i zapolni krožno združljivo zaporedje T, če se razteza v desno in v levo v vsakem rezu T/i, i ± L Zvita družina T nasiti tlakovec T, če zaobjame vsa njegova nujna križišča, t. j. tcr(T) = \T\. Posledica 13. Naj bo T = (T0,..., Th ..., Tm) krožno združljivo zaporedje tlakovcev in T zvita družina v Th ki zapolni T. Če je T popoln ravninski tlakovec za vsak % = 0,... ,m, % ^ l, in je m > 4|^| - 2, potem velja cr(oT) > \T\. Enakost velja vedno, ko T nasiti Tt. S pomočjo posledice 13 v nadaljevanju konstruiramo prekrižno-kritične grafe, katerih povprečna stopnja je blizu šest. Najprej pa se posvetimo oviri, ki omogoči konstrukcijo prekrižno-kritičnih grafov s povprečno stopnjo blizu tri. Naj bo V = {Pi,P2,..., Pn} množica prečnih poti v T, za katero velja A(Pi) < \{Pj) in p(Pi) > p(Pj) za i < j. Poti naj bodo paroma disjunktne, s 128 Razširjeni povzetek razen parov P1,P2 in Pn_u Pn, za katera zahtevamo zgolj povezavno disjunk-tnost. Za m G V(PX) n V(P2) in v G V(P„_i) n V(Pra) pravimo, da je m levo od t; (prim. sliko 3), če obstajata notranje disjunktni poti Qu in Qv od u do t; z naslednjimi lastnostmi: (s.i) na poti Qu obstajajo vozlišča u^u^u?,^,... ,un,u'n v tem vrstnem redu, (s.ii) na poti Qv obstajajo vozlišča v1,v'1,v2,v'2,..., vn, v'n v tem vrstnem redu, (s.iii) u = U\ = u[ = u2 = V\ in v = u'n = v'n_l = vn = v'n, (s.iv) v'l,v2,v'2,u'2 L Pi n P2 in Vn.!,«„_!,<_!,Un (")-!. Razširjeni povzetek 129 \ -•--------------- ¦»¦ J- - ---------------•- \ (a) (b) Slika 4: (a) Tlakovec SV. (b) Tlakovska risba S7 z 20 križišči. V dokazu usmerimo poti P; od leve proti desni steni. Najprej pokažemo, da lahko predpostavimo, da sliki vsakih dveh poti delita največ eno točko. To da skupaj z usmeritvijo povezav risbi dovolj strukture, da lahko poiščemo novo križišče na povezavah poti Qu in Qv, pri čemer sta u G V(PX) n V{P2) in v E V{Pn-i) n V(Pn) vozlišči, kjer se v tlakovski risbi sekata sliki teh dveh parov poti (če katera od teh točk ne bi bila vozlišče, bi bilo križišč že dovolj). Poleg zvitih parov in zvitih stopničastih trakov definiramo še več drugih ovir: podvojena vozlišča, kolesne ovire, mostove, prečne pare, prepletene pare, ter eno- ali dvostranske trinožnike. Vse zagotavljajo vsaj eno ali dve križišči v tlakovski risbi. V delu uporabimo le kolesno oviro, s katero si pomagamo pri dokazovanju prekrižnega števila nekaterih kartezičnih produktov. Konstrukcije Bralec bo brez težav eksaktno opisal tlakovec Sn, n > 3, katerega primer je za n = 7 prikazan na sliki 4 (a). Stopničasti tlakovec širine n > 3, ki je popoln ravninski tlakovec, dobimo iz Sn s stiskanjem nekaj (morda nič) krepkih povezav Sn. Stopničasto zaporedje širine n je zaporedje tlakovcev lihe dolžine, v katerem stopničasti tlakovci širine n alternirajo z obrnjenimi stopničastimi tlakovci širine n. Vsako stopničasto zaporedje je krožno združljivo in tlakovec, ki ga dobimo s spojem zvitja takega zaporedja, vsebuje zvit stopničast trak. Z uporabo lerne 8, posledic 11 in 12 ter izreka 14 dokažemo naslednjo trditev: Trditev 15. Naj bo T stopničasto zaporedje širine n in lihe dolžine m > 4g) - 5. Graf G = o(T l ) je prekrižno-kritičen s prekrižnim številom cr(G) = (2) ~ L 130 Razširjeni povzetek 2w + 1 tlakovcev . (a) A B C P1 Pi Qi Ri Si Pi+1 S2w+1 D E F G (b) Slika 5: (a) Tlakovec H1, gradnik grafa H(1,s). (b) Optimalna tlakovska risba H0. S pomočjo krožnih spojev stopničastih zaporedij lahko pozitivno odgovorimo na Salazarjevo vprašanje za vsak r G (3,4), kjer je r = 3 + § in sta a in b različne parnosti. Če sta enake parnosti, potem bi morala biti dolžina stopničastega zaporedja tlakovcev soda, krožni spoj takega zaporedja pa ne bi bil prekrižno-kritičen graf. Naj bo Hw tlakovec, ki je za w = 1 predstavljen na sliki 5 (a). Zgrajen je iz podtlakovcev, predstavljenih s prekinjenimi črtami, ki ju spojimo z zaporedjem 2w + 1 podtlakovcev, od katerih je eden predstavljen s krepkimi črtami. Vozlišča leve (desne) stene tlakovca Hw so obarvana črno (belo). Hw je popoln ravninski tlakovec. Oznaka H{w, s) = (Hw,..., Hw) naj predstavlja zaporedje teh tlakovcev dolžine s, H(w,s) = o(H{w,s)t) pa naj bo krožni spoj zvitja takega zaporedja. V tlakovcu Hw lahko najdemo družino zvitih parov, ki ga nasiti in zapolni zaporedje H{w, s), zato po posledicah 12 in 13 velja naslednja trditev: Trditev 16. Za k = 32w2 + 56w + 31 in s > 4k - 1 je graf H (w, s) prekrižno-kritičen graf s prekrižnim številom k. Za d, d' > 3 naj Kd>d> predstavlja polni dvodelni graf s pravilno obarvanimi vozlišči: vozlišča stopnje d naj bodo črna in vozlišča stopnje d' naj bodo bela. Za p > 1 naj družina K{d, d',p) predstavlja grafe z obarvanimi vozlišči, ki jih dobimo iterativno z K(d, d', 1) = {Kd>d,} in K(d, d',p) = \JG&i(d,d>,P-i) G VlQV2 Kd>d>. Pri tem sta vx in v2 črni vozlišči v G (oz. Kd>d>). Če velja d='d' = 3, je ^ Razširjeni povzetek 131 lahko katerokoli vozlišče. Pri šivanju grafov ohranimo barve vozlišč, zato grafi v K{d, d',p) niso pravilno obarvani zap > 2. Za take grafe z induktivno uporabo izreka 7 (iii) pokažemo, da so vsa črna vozlišča aktivna. Tako po izreku 7 (ii) oz. po ustrezni trditvi za vozlišča stopnje tri velja naslednja trditev: Trditev 17. Za d, d' > 3 je vsak graf G G K(d,d',p) enostaven 3-povezan prekrižno-kritičen graf s prekrižnim številom cr(G) = pcr{Kdtd,). Jaeger je pokazal, da ima vsak 3-povezan kubičen graf s prekrižnim številom ena kromatični indeks tri. Grafi iz družine K(3, 3,p) v šivu s Petersenovim grafom zagotavljajo, da ni mogoča posplošitev Jaegrovega rezultata na grafe s prekrižnim številom enakim k za noben k > 2. Družine S(n,m,c), H(w,s), K(3, 3,p) in K(3, 5, q) uporabimo v razrešitvi Salazarjevega vprašanja in hkratnem kombiniranju odgovora z rezultati Širana in Kochola. Izrek 18. Naj bo r G (3, 6) racionalno število. Obstaja zvezna konveksna funkcija f : (3,6) -»¦ R+, tako da za vsako celo število k > f(r) obstaja neskončna družina enostavnih 3-povezanih prekrižno-kritičnih grafov s povprečno stopnjo r in prekrižnim številom k. Izrek dokažemo konstruktivno za /(r) = 240 + ^ + S + I6(^ + Ä- Pri tem sestavimo sedemparametrično družino T{n,m,c,w,s,p,q), ki vsebuje šive grafov iz S(n,m,c), H(w,s), 71(3, 3,p) in K(3, 5, q). Grafi H(w,s) omogočajo povprečno stopnjo blizu šest in grafi iz S omogočajo povprečno stopnjo blizu tri. Disjunktna unija dveh takih grafov sestavljenih iz sorazmernega števila tlakovcev bi imela predpisano povprečno stopnjo in prekrižno število. Ko taka grafa sešijemo, šiv pokvari vzorec, ki zagotavlja predpisano povprečno stopnjo. To nepravilnost odpravimo z grafi iz K, s katerimi zagotovimo tudi predpisano prekrižno število. Ker imajo vsa vozlišča stopnje tri v navedenih grafih dve usklajeni butari, so grafi iz T{n,m,c,w,s,p,q) prekrižno-kritični po izreku 7 in trditvah 15, 16 in 17, kadar je zadoščeno naslednjim pogojem: n>3,m=2m' + l,m'> 2 g), c > 0, c < 2m(n -3),w>0,s> 4(32w2 + 56w + 31), p>lmq>l. Prekrižno število omenjenih grafov je enako k= n +32w 2 + 56w+p + 4q + 30, (1) povprečna stopnja pa - 4(m'(6n- 11) + 3n + 3p + 3q + is - c-7) 2m'(4n - 7) + 4n + 4sw + 9s + 4p + 6q - c - 9' (2) 132 Razširjeni povzetek Slika 6: Struktura znanih velikih fc-prekrižno-kritičnih grafov. Enakost (1) določi p z vrednostmi predpisanega prekrižnega števila k in ostalih parametrov. Da bosta ciklični strukturi rastli sorazmerno, določimo s in m kot linearni funkciji novega parametra t, ki določa velikost grafa. Ko te vrednosti vstavimo v (2), uporabimo c za izničenje členov imenovalca, ki so neodvisni od t. S parametrom q izničimo take člene v števcu. Vrednost t se pokrajša, kar zagotovi, da bodo grafi za vsak t imeli predpisano povprečno stopnjo, ki jo določimo z vrednostima koeficientov linearnih funkcij. Na koncu z vrednostmi parametrov ninw ter konstantnih členov linearnih funkcij poskrbimo, da je zadoščeno prej naštetim pogojem. Dobljena družina T (a, b, k) = \JZk r(™, mt, c, w, st,p, q) je neskončna družina grafov s povprečno stopnjo r = 3 + f in prekrižnim številom k. Funkcija / je konveksna na intervalu (3,6), saj je vsota funkcij, ki so konveksne na tem intervalu. Ta lastnost pove, da je Nj = max{/(n), /(r2)} univerzalna spodnja meja za vrednost k za vsa racionalna števila r s poljubnega zaprtega intervala / = [r1}r2] C (3, 6). Struktura prekrižno-kritičnih grafov Oporowski [87] je pokazal, daje mogoče velike 2-prekrižno-kritične grafe dobiti kot krožne spoje dolgih zaporedij nekaj različnih vrst tlakovcev. Konstrukcija prekrižno-kritičnih grafov s šivanjem pokaže, da za k > 4 taka klasifikacija ne obstaja, saj bi lahko s šivanjem pridobili poljubno mnogo različnih tlakovcev z enakim tlakovskim prekrižnim številom. Ta konstrukcija tudi pokaže, da je za velike k mogoče dobiti prekrižno-kritične grafe s šivanjem manjših takih grafov na nekritične grafe z ustreznim vozliščnim pokritjem. Nova spoznanja o strukturi prekrižno-kritičnih grafov prikazuje slika 6. Glede stopenj vozlišč v fc-prekrižno-kritičnih grafih ostajata odprti naslednji vprašanji: Razširjeni povzetek 133 Vprašanje 19 ([105]). Ali obstaja celo število k > 0 in neskončna družina enostavnih 5-regularnih 3-povezanih k-prekrižno-kritičnih grafov? Vprašanje 20. Ali obstaja k > 0 in neskončna družina enostavnih 3-povezanih k-prekrižno-kritičnih grafov s povprečno stopnjo šest? Argumente, s katerimi Richter in Thomassen v [105] pokažeta, da za k > 0 obstaja le končno mnogo fc-prekrižno-kritičnih grafov z minimalno stopnjo šest, je mogoče uporabiti za grafe z omejenim številom vozlišč stopnje različne od šest. Tako lahko predpostavimo, da bi družina, ki bi pozitivno odgovorila na vprašanje 20, vsebovala grafe s poljubno mnogo vozlišči stopnje, večje od šest. Vendar pa se v znanih neskončnih družinah fc-prekrižno-kritičnih grafov le vozlišča stopenj tri, štiri in šest pojavljajo poljubnomnogokrat. Tako predlagamo naslednje vprašanje, odgovor na katerega bi bil korak v smeri razrešitve vprašanj 19 in 20. Vprašanje 21. Ali obstaja tak k > 0, da za vsako celo število n obstaja enostaven 3-povezan k-prekrižno-kritičen graf Gn z več kot n vozlišči stopenj različnih od tri, štiri in šest? Šiv grafa K3>d in grafov iz znanih neskončnih družin fc-prekrižno-kritičnih grafov pokaže, da obstajajo neskončne družine prekrižno-kritičnih grafov s poljubno mnogo vozlišči stopnje d. Vendar prekrižno število grafov teh družin narašča s številom takih vozlišč. Kartezični produkti Naj G« predstavlja suspenzijo reda i grafa G, t. j. popolni spoj grafa G in praznega grafa na i vozliščih {v1}...,Vi}, ki jih imenujemo temena suspenzije G«. Za multimnožico L C V {H) naj G UL H predstavlja pokriti kartezični produkt grafov G in H, t. j. graf, ki ga dobimo z dodajanjem novega vozlišča v' k grafu G D H za vsako vozlišče v G L, pri čemer v' povežemo z vsemi vozlišči v G D {v}. Vozlišče v' imenujemo pokrov vozlišča v. Ko L vsebuje natanko vsa vozlišča stopnje ena v H, uporabimo oznako GUH namesto G DL H. Za v G V (H) definiramo L(v) := degH(w) + Xl(v), kjer Xl(v) predstavlja mnogo-kratnost vozlišča v v multimnožici L. Povezava uv G E(H) je neuravnovešena, če je L(u) = L(v), ß(H) pa predstavlja število neuravnovešenih povezav v H. V tem kontekstu z induktivno uporabo šivanja optimalnih risb suspenzij pokažemo naslednji izrek: 134 Razširjeni povzetek Izrek 22. Naj ho T drevo reda m>2,LC V (T) multimnožica z L(v) > 2 za vsak v E V {T) in G graf reda n z dominirajočim vozliščem v. DeGniramo B= Y cr(G^). veV(T) Potem velja B < cr(G DL T) < B+ß{T) f1"1. Kadar grupa avtomorGzmov G deluje kot polna simetrična grupa na sosedih vvG, velja enakost cr(G DL T) = B. Zgornji izrek velja za vsak graf G, če zahtevamo L(v) > 3. Ta pogoj zagotavlja zadostno število butar v suspenziji grafa G. Preprosta posledica izreka je, da velja cr(G D Pm) = (m+1) cr(G(2)) za graf G z dominirajočim vozliščem m > 0. Dobimo tudi meje za prekrižno število navadnega kartezičnega produkta: za graf G reda n z dominirajočim vozliščem in za m > 2 velja (m - 1) cr(G(2)) < cr(G D Pm) < (m - 1) cr(G(2)) + 2 fcr(G«) +(n-1\\. Ta trditev omogoča asimptotično določanje prekrižnega števila kartezičnega produkta grafov s potmi. Za produkte ciklov z drevesi lahko pokažemo naslednjo trditev, pri kateri bistveno uporabimo Kleitmanove in Woodalove rezultate o prekrižnem številu polnih dvodelnih grafov [65, 134] Posledica 23. Naj za celi števili n in d velja eden od pogojev (i) 3 < n in 1 < d < 6, (ii) 3 < n < 6 in 1 < d, (iii) 3 < n < 8 in 1 < d < 10 oz. (iv) 3 < n < 10 in 1 < d < 8. Potem za vsako drevo T z maksimalno stopnjo d in za dv = degT(w); v G V {T), velja: Z^2 2 2 2 »ev(r) Suspenzija zvezde S^ je izomorfna polnemu tripartitnemu grafu KlAn, ki ga dobimo s stiskanjem ene povezave v Kd+l,n+l. Graf Sn D Sd je subdivi-zija grafa S$. Tako lahko prekrižno število kartezičnega produkta drevesa in zvezde s pomočjo izreka 22 zapišemo kot vsoto prekrižnih števil kartezičnih produktov dveh zvezd: cr(SraDT)= V cr(Kld n). veV(T), dv>2 S pomočjo Asanovega rezultata o prekrižnem številu K1>3>n lahko pokažemo naslednje: Razširjeni povzetek 135 Posledica 24. Za celo število n > 1 in podkubično drevo T z n2 vozlišči stopnje dve in n3 vozlišči stopnje tri velja cr(Sn D T) = Za poljubno drevo T velja (n2 + 2n3) -—- + n^ cr(S3 D T) = V — 2------ + lV Z^ 2 2 Poseben primer posledice 24 sta JendroP in Ščerbova domnevala v [57]. Posledica 25. cr(Sra D Pm) = (m - 1) [f J [2f±J zam,n> 1. Tudi pri kartezičnemu produktu koles si lahko pomagamo s sub divizij ami, vendar moramo dodati za en cikel povezav, s čimer povečamo prekrižno število grafa. Najprej formaliziramo to operacijo: naj bo vr permutacija podmnožice povezav F C E{G). iv-subdivizija Gn grafa G je graf, ki ga dobimo iz G s subdividiranjem povezav e G F z vozliščem ve in dodajanjem novih povezav {vev^e) I e G F}. Če F predstavlja množico povezav, sosednjih z nekim vozliščem, in vr ciklično rotacijo povezav okrog tega vozlišča v neki optimalni risbi G, potem vr-subdivizija ne spremeni prekrižnega števila grafa. Če pa nekaj povezav izpustimo in nam ostanejo vsaj tri, potem se v primeru, da pri tem vozlišču obstaja butara, prekrižno število poveča vsaj za ena. S pomočjo te ugotovitve ter lerne, da za n > 3 velja cr(wi2)) = [f J [2f±J + 1, ugotovimo natančno prekrižno število kartezičnega produkta kolesa s potjo: Posledica 26. cr(Wn D Pm) = (m - 1) ([f J [^-\ + l) + 2 za m > 2, n > 3. Z analizo primerov ugotovimo tudi cr(Vy3(3)) = 5, iz česar sledi zametek analoga posledice 24 za kolesa: Posledica 27. cr(W3 D T) = m + 2n2 + 5n3 za podkubično drevo T z m vozlišči stopnje i, i = 1,2,3. Minorsko prekrižno število V tem razdelku s pomočjo tehnik za izdelavo minorsko monotonih invariant, ki jih je študiral Fijavž [38], uvedemo minorsko monotono različico prekrižnega števila. Rezultati razdelka so osnovani na raziskavah Fijavža, Moharja in avtorja te disertacije, objavljenih v [20]. Pred tem delom je bilo znanih le malo 136 Razširjeni povzetek Slika 7: mer kot razširitev cr. rezultatov, ki so povezovali prekrižno število z grafovskimi minorji. Moreno in Salazar sta objavila spodnjo mejo za prekrižno število grafa, ki temelji na prekrižnem številu njegovega minorja majhne maksimalne stopnje [86]. Njun rezultat posplošimo v nadaljevanju. Robertson in Seymour [109] sta določila prepovedane minorje za lastnost biti minor grafa s preknžmm številom največ ena. Strukturo risb grafov, ki izhaja iz te lastnosti, raziščemo tudi za večja prekrižna števila in jo uporabimo za izboljšavo spodnje meje, ki izhaja iz Eu-lerjeve formule. Minorsko prekrižno število iskanega grafa G v ploskvi E definiramo kot najmanjše prekrižno število grafa, ki vsebuje G kot minor, mcr(G, E) := min {cr(H, E) \ G g(G)-g(E) inmcr(G,E) > g(G)-2g(E). Za neorientabilno ploskev E roda g(E) velja mcr(G, E) > g {G) - g(E). Kadar rod grafa ni znan, si lahko pomagamo z naslednjo spodnjo mejo, ki sledi iz Eulerjeve formule. Tudi v dokazu te meje uporabimo lepljenje projektivnih ravnin in ročajev namesto križišč: Trditev 30. Za graf G zn= \V(G)\, m = \E(G)\ in notranjim obsegom r ter ploskev E Eulerjevega roda g velja mer (G, E) > r-^m -n-g + 2. To spodnjo mejo lahko izboljšamo z uporabo strukture grafov z omejenim prekrižnim številom, prim. izrek 36. Tehniko menjave križišč za projektivne ravnine in ročaje lahko uporabimo tudi za primerjavo prekrižnih števil v različnih ploskvah: Trditev 31. Neenakost mcr(G, S) < max(0,mcr(G) - g(E)) velja za vsako ploskev S in vsak graf G, kjer g(E) predstavlja (nejorientabilni rod ploskve E. Naj bo S ploskev in k pozitivno celo število. Družina ploskev Eu...,Ek je dekompozicija ploskve S, S = Ei# • • • #Efc, če je E homeomorfna povezani vsoti Ei,...,Efc. Izrek 32. Naj bo E ploskev in G graf z bloki Gl}...,Gk. Potem velja k r k } Y, mcr(Gt, E) < mcr(G, E) < min l J] mcr(Gt, Et) E = Ei# • • • #Efc l . i=\i=\ Razširjeni povzetek 139 Povezave iz drevesa Tv, v G V (G), se v realizirajoči risbi ne sekajo, zato je število križišč med povezavami iz istega bloka strogo manjše od števila vseh križišč in spodnja meja sledi. Pri zgornji meji uporabimo drevo blokov grafa, da induktivno sestavimo risbo grafa G v S kot povezano vsoto risb grafov G; v ploskvah S;. Ker ima sfera §0 le trivialne dekompozicije, za vsak graf velja enakost mcr(G) = Etimcr(G*)- Struktura grafov z omejenim mer Naj družina F(k, S) predstavlja množico minimalnih prepovedanih minorjev za uj(k,E), F(k) in u(k) pa naj označujeta F {k, So) in u{k,So). Grafi v u(0, S) imajo preprost topološki opis — to so natanko grafi, ki jih je mogoče vložiti v ploskev S. Robertson in Seymour sta opazila, da je na podoben način mogoče opisati grafe iz u(l): to so natanko grafi, ki jih je mogoče vložiti v projektivno ravnino z lično širino dve [109]. S pomočjo tega opisa sta določila družino prepovedanih minorjev F(l) za u(l). Ta vsebuje natanko 41 grafov: Gl}..., G35 so prepovedani minorji za vložitev v projektivno ravnino, Qi,..., Q6 pa so projektivni grafi, ki jih dobimo iz Petersenovega grafa z YA, AY transformacijami. V nadaljevanju bomo pokazali, da ima vsaka družina oj(k, S) podoben topološki opis. Naj bo 7 enostranska enostavna sklenjena krivulja v neorientabilni ploskvi S Eulerjevega roda g. Z rezom S vzdolž 7 in lepljenjem diska na dobljeno mejo dobimo ploskev S/7, katere Eulerjev rod je g - 1. Pravimo, da smo S/7 dobili iz S z izničenjem projektivne ravnine pri 7. Množico paroma neprekrižanih enostranskih enostavnih sklenjenih krivulj T = {7i,...,7fc} v neorientabilni ploskvi S imenujemo k-sistem v S. Za različni 7i,7i G T sta ploskvi (S/^)^- in (S/7i)/7i homeomorfni, torej zaporedje, v katerem izničimo krivuljam pripadajoče projektivne ravnine, ni pomembno. Tako lahko definiramo E/T := E/71/.. ./7*. Pravimo, da je k-sistem T v S orientirajoči k-sistem, če je ploskev E/T orientabilna. Naj bo D risba grafa G v neorientabilni ploskvi S z največ c križišči. Če obstaja (orientirajoči) fc-sistem T v S, tako da vsaka krivulja 7 G T seka D v največ dveh vozliščih, je risba D {orientirajoče) (c, k)-izrojena, množico T pa imenujemo (orientirajoči) k-sistem za D. Če je c = 0, potem je D k-izrojena vložitev. Vložitev v projektivno ravnino je 1-izrojena natanko tedaj, kadar ima lično širino največ dve. Z zamenjavo križišč za projektivne ravnine za prvo oz. z izničevanjem projektivnih ravnin za drugo smer pokažemo naslednjo lemo: Lema 33. Naj bo S (orientabilna) ploskev Eulerjevega roda g in naj bo k > 1 celo število. Potem za vsak le {!,..., k} družina u(k, S) vsebuje natanko tiste grafe iz G Ecü(k-l, Nfl+J), za katere obstaja graf G, ki vsebuje G kot minor 140 Razširjeni povzetek in ga je mogoče narisati v neorientabilni ploskvi Ng+t Eulerjevega roda g + l z (orientirajočo) izrojenostjo (k -1,1). Za naslednjo trditev opazimo, da se krivulje v fc-sistemu T lahko dotikajo. Če več krivulj iz T seka isto povezavo vložitve, jih pri stiskanju povezave lahko premaknemo, da se dotikajo v stisnjenem vozlišču. Lema 34. Naj bo G graf z (orientirajočo) k-izrojeno vloživijo v ploskvi E. Če je G ploskovni minor G, potem je inducirana vložitev G tudi (orientirajoče) k-izrojena. Iz lern 33 in 34 sledi naslednji izrek: Izrek 35. Naj bo S (orientabilna) ploskev Eulerjevega roda g in naj bo k > 1 celo število. Potem družina u(k, E) vsebuje natanko vse grafe, ki jih je mogoče vložiti v neorientabilno ploskev Ng+k Eulerjevega roda g + k z (orientirajočo) izrojenostjo k. S pomočjo izreka 35 lahko pokažemo, da za vsak graf G G u(k, E) obstaja graf H eoj(0,E), tako da je G mogoče dobiti iz k z identifikacijo največ k parov vozlišč. Izrek lahko uporabimo tudi za izboljšavo spodnje meje za minorsko prekrižno število, ki izhaja iz Eulerjeve formule (trditev 30). Izrek 36. Naj bo G enostaven graf z n = \VG\, m = \EG\ in E ploskev Eulerjevega roda g. Potem velja mcr(G, E) > \(m - 3(n + g) + 6). Za dokaz izreka potrebujemo dve tehnični lemi. S prvo pokažemo, da lahko fc-sistem T, katerega krivulje se vse paroma dotikajo v dveh točkah, v ploskvi S določa največ k - 1 diskov, ki imajo za meje le dva loka krivulj iz T. k-izrojeno vložitev grafa G v neko ploskev nato dopolnimo z 2k povezavami, ki jih določajo krivulje fc-sistema. Z odstranitvijo največ k od teh povezav se znebimo vseh lic dolžine dve. Na preostanku razširjenega grafa uporabimo Eulerjevo formulo in izrek 36 sledi. Uporaba Prej navedene meje v tem razdelku uporabimo na več družinah grafov. Za polne grafe pokažemo: Trditev 37. \\(n - 3)(n - 4)] < mcr(Kn) < [\(n - 5)2J +4zan>9. Razširjeni povzetek 141 Ti T2 T3 T± T5 T6 Slika 9: Risbi grafov z minorjema K10 in K11. Trditev sledi iz izreka 29 ter konstrukcije, prikazane na sliki 9. Za 3 < n < 8 je spodnja meja natančna, tako velja mcr(Kn) = 0 za n < 4 ter mcr(K5) = 1, mcr(K6) = 2, mcr(K7) = 3 in mcr(K8) = 5. Naslednjo trditev pokažemo z opazovanjem risb Kn_x v optimalni risbi Kn. Posledica 38. Naj bo S neka ploskev in cn = mc^™{f zan>3. Zaporedje {cn}n=3 Je nepadajoče in limita Coo := lim^«, cn obstaja. Za §0 je c» G [\,\] . Za polne dvodelne grafe pokažemo naslednje meje: Trditev 39. \{m -2){n- 2) < mcr(Km,n) < (m - 3)(n - 3) + 5 za 4 < m < n. Spodnja meja sledi iz izreka 29. Za m = 3, 4 je spodnja meja natančna: mcr(X3)ra) 2 in mcr(K4,n) n 2. Z uporabo izreka 28 in z najboljšimi znanimi spodnjimi mejami za prekrižno število hiperkock pokažemo naslednje meje: Trditev 40. Za n > 4 velja max ((n - 4)2ra"2 + 2, 4 (| 4ra - 2ra+1) - 2n+l) < mcr(Qn)m,inzam>7,n> \{m+\){m + 2). _ _ 142 Razširjeni povzetek Izjavljam, da je disertacija plod lastnega raziskovalnega dela. Drago Bokal