Pair Crossing Number Lemma and Variants in Graph Theory
Explore the crossing lemma for the pair crossing number by Eyal Ackerman and Marcus Schaefer. Understand the minimum edge crossings in a graph drawing and various crossing numbers like pcr and ocr. Discover the significance of adjacent crossings and other related lemmas in graph theory.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
A crossing lemma for the pair-crossing number Eyal Ackerman and Marcus Schaefer
weaker than advertised A crossing lemma for the pair-crossing number Eyal Ackerman and Marcus Schaefer
a variant of A crossing lemma for the pair-crossing number Eyal Ackerman and Marcus Schaefer
The crossing lemma The crossing number of a graph ?, cr(?), is the minimum number of edge crossings in a drawing of ? in the plane. Crossing Lemma: For every graph ? with ? vertices and ? 4? edges cr(?) ? ?3/?2. [Ajtai, Chv tal, Newborn, Szemer di 1982; Leighton 1983] Tight, up to ?. 1 64 33.75 31.1 1 1 1 29 0.0345 ? 0.09 Pach & T th 97 folklore Pach & T th 97 Pach et al. 06 A. 2013
The crossing lemma The crossing number of a graph ?, cr(?), is the minimum number of edge crossings in a drawing of ? in the plane. Crossing Lemma: For every graph ? with ? vertices and ? 4? edges cr(?) ? ?3/?2. [Ajtai, Chv tal, Newborn, Szemer di 1982; Leighton 1983] Tight, up to ?. 1 64 33.75 31.1 Proof: cr ? ? 3? Consider a drawing with cr(?) crossings Pick every vertex with probability ? and get ? Ex ? = ??, Ex ? = ?2?, Ex(cr ? ) Ex(? ) 3 Ex(? ) Plug in the expected values and set ? = 4?/? 1 Ex cr(? ) ?4cr ? 1 1 1 29 0.0345 ? 0.09 Pach & T th 97 folklore Pach & T th 97 Pach et al. 06 A. 2013
Other crossing numbers cr(?) min number of crossings when ? is drawn with straight-line edges. pcr(?) min number of pairs of edges that cross. ocr(?) min number of pairs of edges that cross oddly. And many more [Schaefer 2013]
Adjacent crossings Are adjacent crossings redundant? Tutte: crossings of adjacent edges are trivial, and easily got rid of . True for cr but not necessarily for other variants. Pach and T th: Rule +: Adjacent crossings are not allowed. Rule -: Adjacent crossings are not counted. Rule 0: Adjacent crossings are allowed and counted. Fulek et al. , Adjacent crossings do matter, GD 2011: there are graphs ? such that ocr-(?) < ocr(?).
Other crossing lemmas ?3 ocr-? ocr ? pcr ? pcr+(?) cr(?) cr (?) 64?2 Using the probabilistic proof and the strong Hanani-Tutte Theorem 1 Thm: pcr(?) 34.2 ?3/?2.* 1 Thm: pcr+(?) 34.2 ?3/?2.* * If ? is not too sparse.
Improving via local crossing number The local crossing number of a graph ?, lcr(?), is the minimum ? such that ? can be drawn with at most ? crossings per edge. Or: lcr ? = minimum ? such that ? is ?-planar. Improving the crossing lemma: Prove that if lcr ? is small then ? is sparse . E.g., if lcr ? 1 then ? 4(? 2). Use it to get a weak bound cr ? ? ? ? ?. E.g., cr ? 2 ? 4? 2? 8? Use the weak bound instead of cr ? ? 3? in the probabilistic proof of the crossing lemma.
Improving via local crossing number (2) lcr ? = 0 ? 3 ? 2 [Euler] lcr ? 1 ? 4(? 2) [Pach & T th 1997] lcr ? 2 ? 5(? 2) [Pach et al. 2006] lcr ? 3 ? 5.5(? 2) lcr ? 4 ? 6(? 2) [A. 2013] lcr ? ? ? 3.81 ??
The local pair-crossing number The local pair-crossing number of a graph ?, lpcr(?), is the minimum ? such that ? can be drawn with every edge crossing at most ? other edges (each of them possibly more than once). Clearly, lpcr ? lcr(?). It can happen that lpcr ? < lcr(?): lpcr ? = 4 lcr ? = 5
lpcr ? vs. lcr ? lcr ? < 2lpcr(?)[Schaefer & tefankovi 2004] Thm: If lpcr ? 2 then lpcr ? = lcr(?). Cor: lpcr ? = 0 ? 3 ? 2 lpcr ? 1 ? 4 ? 2 lpcr ? 2 ? 5 ? 2 Just saw: lpcr ? = 4 lcr ? = 4. Open: lpcr ? = 3 lcr ? = 3 ? If true, then lpcr ? 3 implies ? 5.5(? 2). Thm: if lpcr ? 3 then ? 6(? 2).
Improving the crossing lemma for pcr+ Using the bounds on the size of graphs with small lpcr we get: pcr+(G) pcr ? 4? 18? Plugging this bound into the probabilistic proof yields pcr+(?) 1 34.2 ?3/?2for ? 6.75?.
Proving lpcr ? 2 lcr ? 2 lcr ? 3 since lcr ? < 2lpcr(?) ? a drawing of ? with the least number of crossings such that lcr ? 3. Suppose that ? is crossed 3 times: No consecutive crossings with the same edge:
Proving lpcr ? 2 lcr ? 2 lcr ? 3 since lcr ? < 2lpcr(?) ? a drawing of ? with the least number of crossings such that lcr ? 3. Suppose that ? is crossed 3 times: Crossing pattern must be ???:
Summary and open problems A pair-crossing lemma: For every graph ? with ? vertices and ? 6.75? edges pcr+ (?) 1 34.2 ?3/?2 Does it hold for pcr? Is it true that pcr ? = pcr+(?)? Is it true that pcr ? = cr(?)? Known: cr ? = ?((pcr ? )3/2) [Matousek 2013]
Summary and open problems (2) lcr ? < 2lpcr(?) Is it true that lcr ? < poly(lpcr ? ) ? Thm: If lpcr ? 2 then lpcr ? = lcr(?). There is ? such that lpcr ? = 4 < lcr ? = 5. Open: lpcr ? = 3 lcr ? = 3 ? Thm: if lpcr ? 3 then ? 6(? 2). What about the local odd-crossing number? locr ? = 1 lcr ? = 1 ?
