Fox, Jacob and Pach, János and Suk, Andrew (2021) On the Number of Edges of Separated Multigraphs. In: International Symposium on Graph Drawing and Network Visualization. Lecture Notes in Computer Science (12868). Springer Science and Business Media B.V., pp. 223-227. ISBN 9783030929305
|
Text
10327409.pdf Download (187kB) | Preview |
Abstract
We prove that the number of edges of a multigraph G with n vertices is at most O(n2log n), provided that any two edges cross at most once, parallel edges are noncrossing, and the lens enclosed by every pair of parallel edges in G contains at least one vertex. As a consequence, we prove the following extension of the Crossing Lemma of Ajtai, Chvátal, Newborn, Szemerédi and Leighton, if G has e≥ 4 n edges, in any drawing of G with the above property, the number of crossings is Ω(e3n2log(e/n)). This answers a question of Kaufmann et al. and is tight up to the logarithmic factor. © 2021, Springer Nature Switzerland AG.
| Item Type: | Book Section |
|---|---|
| Additional Information: | Conference code: 270329 Export Date: 18 January 2023 Correspondence Address: Suk, A.; University of California at San DiegoUnited States; email: asuk@ucsd.edu Funding details: National Science Foundation, NSF, DMS-1855635 Funding details: European Research Council, ERC, DMS-1952786 Funding details: Austrian Science Fund, FWF, Z 342-N31 Funding details: Ministry of Education and Science of the Russian Federation, Minobrnauka, 075-15-2019-1926 Funding details: Nemzeti Kutatási Fejlesztési és Innovációs Hivatal, NKFIH, K-176529, KKP-133864 Funding text 1: J. Fox—Supported by a Packard Fellowship and by NSF award DMS-1855635. J. Pach—Supported by NKFIH grants K-176529, KKP-133864, Austrian Science Fund Z 342-N31, Ministry of Education and Science of the Russian Federation MegaGrant No. 075-15-2019-1926, ERC Advanced Grant “GeoScape.” A. Suk—Supported by an NSF CAREER award, NSF award DMS-1952786, and an Alfred Sloan Fellowship. |
| Uncontrolled Keywords: | PROPERTY; Directed graphs; LENSES; Noncrossing; Multigraphs; Multigraphs; Crossing lemma; Crossing lemma; |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 22 Nov 2023 16:46 |
| Last Modified: | 22 Nov 2023 16:46 |
| URI: | http://real.mtak.hu/id/eprint/180661 |
Actions (login required)
 |
Edit Item |
