CrossingNumberandApplications

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,Crossing Number and Applications,Greg Aloupis,(based on a,seminar,by Janos Pach and a journal,paper,by Tamal Dey),1,Whats a crossing number?,X(G),is the minimum number of edge crossings in any planar drawing of,G.,if X(G) = 0, then G is planar.,if X(G) = 1, then there are 41 minors that G does not contain (Robertson-Seymour 93),if X(G) = 2, we dont know.,2,Theorem: if e,4v,X(G),ke,3,/v,2,First by Ajtai-Chvatal-Newborn-Szemeredi in 82, (k=1/100), and by Leighton 83.,k has been raised over the years, but wont exceed 8.,3,Proof: if e,4v,X(G),e,3,/64v,2,Lemma: X(G), e-(3v-6) e-3v,Pick every vertex with probability p and obtain a subgraph G.,Now, EX(G) Ee - 3Ev so,p,4,X(G) p,2,e - 3pv .,X(G) is maximized when p,4v/e.,4,Applications,Number of incidences between n points and m lines is O(n+m+ n,2/3,m,2/3,),Szemeredi,-Trotter 83,Number of unit distances formed by n points in the plane is O(n,4/3,),Spencer-,Szemeredi,-Trotter 84,Number of distinct distances is cn,4/5,/,log,c,n,Chung-,Szemeredi,-Trotter 92,5,Application IV: dividing lines,Tamal K. Dey 98,6,Application IV: dividing lines,7,Application IV: dividing lines,8,Application IV: dividing lines,9,Application IV: dividing lines,10,Application IV: dividing lines,The result by Dey: there are O(nk,1/3,) k-sets for a planar set of n points.,In the dividing line case, k = n/2, so O(n,4/3,) .,Previous results:,Lovasz 71 gave a bound of O(nk,1/2,).,Pach-Steiger-Szemeredi 89 improved by a log*k factor,11,Suppose we have a planar graph with,e,edges corresponding to dividing lines of the n vertices. We want to prove that,e,is,O(n,4/3,) .,12,A really short “proof ”,Claim: the number of crossings, X, in such a graph is O(n,2,).,in general, O(nk),We know that X(G),e,3,/64n,2,And we assume e4n, otherwise were done already.,O(,n,2,) ,X X(G) e,3,/64n,2,Combining, obtain a bound of O(n,4/3,) for e.,in general, O(nk,1/3,),13,Longer proof:,Our n points in the plane,14,We obtain n lines in dual plane,15,Lines in the plane,16,will map to points in the dual,17,Important above/below relation:,18,More important: intersections,19,Reminder: were looking for lines between points, that have half points above/below,20,Equivalent to looking for “special” convex intersections on the median level in the dual,21,How many special vertices are there on the median level? It can revisit lines, so ?,So heres another approach:,Form n/2 concave chains, starting at x= -, one for each line starting under the median level.,Move along lines from left to right, turning right when hitting the median level (must be at a convex vertex),22,The,median,level,23,The,median,level and example of a,chain,24,Note:,chains,dont overlap or share vertices. They cover all special vertices on,ML,and all intersections below, but dont overlap or cross over,ML,.,25,Remember our graph?,Consider two (dividing) edges that cross.,Their intersection corresponds to a bridge between two chains in the dual,26,Remember our graph?,Consider two (dividing) edges that cross.,Their intersection corresponds to a bridge between two chains in the dual,27,So, the number of bridges between concave chains in the dual is an upper bound on the the number of crossings, X, in our graph.,28,Flash back,Claim: the number of crossings, X, in our graph is O(n,2,).,in general, O(nk),We know that X(G),e,3,/64n,2,O(,n,2,) ,X X(G) e,3,/64n,2,Combining, obtain a bound of O(n,4/3,) for e.,in general, O(nk,1/3,),29,30,The number of bridges between concave chains in the dual is an upper bound on the the number of crossings, X, in our graph.,DONE,Number of bridges is less than the number of intersections among the concave chains, which is O(n,2,).,In general O(nk), Alon-Gyori 86.,Thus X #bridges #intersections ,X X(G) e,3,/64n,2,Combining, obtain a bound of O(n,4/3,) for e.,in general, O(nk,1/3,),32,Summary of proof,Given n points, and e dividing lines (segments),Go to dual: we have n lines,e special intersection points, which are on the median level of the arrangement.,Form n/2 vertex disjoint concave chains that “skim” the median level.,Every intersection among e edges corresponds to a bridge between concave chains.,The number of bridges is at most the number of intersections in the arrangement below median level.,The number of such intersections is at most quadratic.,So e,3,/v,2, X(G) X bridges intersections(e) O(v,2,),So e is O(n,4/3,).,33,Summary of proof,Given n points, and e dividing lines,Go to dual: we have n lines,e special intersection points, which are on the median level of the arrangement.,Form n/2 vertex disjoint concave chains that “skim” the median level.,Every intersection among e edges corresponds to a bridge between concave chains.,The number of bridges is at most the number of intersections in the arrangement below median level.,The number of such intersections is at most quadratic.,So e,3,/v,2, X(G) X bridges intersections(e) O(v,2,),So e is O(n,4/3,).,34,Summary of proof,Given n points, and e dividing lines,Go to dual: we have n lines,e special intersection points, which are on the median level of the arrangement.,Form n/2 vertex disjoint concave chains that “skim” the median level.,Every intersection among e edges corresponds to a bridge between concave chains.,The number of bridges is at most the number of intersections in the arrangement below median level.,The number of such intersections is at most quadratic.,So e,3,/v,2, X(G) X bridges intersections(e) O(v,2,),So e is O(n,4/3,).,35,Summary of proof,Given n points, and e dividing lines,Go to dual: we have n lines,e special intersection points, which are on the median level of the arrangement.,Form n/2 vertex disjoint concave chains that “skim” the median level.,Every intersection among e edges corresponds to a bridge between concave chains.,The number of bridges is at most the number of intersections in the arrangement below median level.,The number of such intersections is at most quadratic.,So e,3,/v,2, X(G) X bridges intersections(e) O(v,2,),So e is O(n,4/3,).,36,Summary of proof,Given n points, and e dividing lines,Go to dual: we have n lines,e special intersection points, which are on the median level of the arrangement.,Form n/2 vertex disjoint concave chains that “skim” the median level.,Every intersection among e edges corresponds to a bridge between concave chains.,The number of bridges is at most the number of intersections in the arrangement below median level.,The number of such intersections is at most quadratic.,So e,3,/v,2, X(G) X bridges intersections(e) O(v,2,),So e is O(n,4/3,).,37,Summary of proof,Given n points, and e dividing lines,Go to dual: we have n lines,e special intersection points, which are on the median level of the arrangement.,Form n/2 vertex disjoint concave chains that “skim” the median level.,Every intersection among e edges corresponds to a bridge between concave chains.,The number of bridges is at most the number of intersections in the arrangement below median level.,The number of such intersections is at most quadratic.,So e,3,/v,2, X(G) X bridges intersections(e) O(v,2,),So e is O(n,4/3,).,38,Summary of proof,Given n points, and e dividing lines,Go to dual: we have n lines,e special intersection points, which are on the median level of the arrangement.,Form n/2 vertex disjoint concave chains that “skim” the median level.,Every intersection among e edges corresponds to a bridge between concave chains.,The number of bridges is at most the number of intersections in the arrangement below median level.,The number of such intersections is at most quadratic.,So e,3,/v,2, X(G) X bridges intersections(e) O(v,2,),So e is O(n,4/3,).,39,Summary of proof,Given n points, and e dividing lines,Go to dual: we have n lines,e special intersection points, which are on the median level of the arrangement.,Form n/2 vertex disjoint concave chains that “skim” the median level.,Every intersection among e edges corresponds to a bridge between concave chains.,The number of bridges is at most the number of intersections in the arrangement below median level.,The number of such intersections is at most quadratic.,So e,3,/v,2, X(G) X bridges intersections(e) O(v,2,),So e is O(n,4/3,).,40,