{
  "id": "2108.11290",
  "version": "v1",
  "published": "2021-08-25T15:21:11.000Z",
  "updated": "2021-08-25T15:21:11.000Z",
  "title": "On the number of edges of separated multigraphs",
  "authors": [
    "Jacob Fox",
    "Janos Pach",
    "Andrew Suk"
  ],
  "comment": "Appears in the Proceedings of the 29th International Symposium on Graph Drawing and Network Visualization (GD 2021)",
  "categories": [
    "math.CO",
    "cs.CG"
  ],
  "abstract": "We prove that the number of edges of a multigraph $G$ with $n$ vertices is at most $O(n^2\\log 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\\'atal, Newborn, Szemer\\'edi and Leighton, if $G$ has $e \\geq 4n$ edges, in any drawing of $G$ with the above property, the number of crossings is $\\Omega\\left(\\frac{e^3}{n^2\\log(e/n)}\\right)$. This answers a question of Kaufmann et al. and is tight up to the logarithmic factor.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-08-25T15:21:11.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "separated multigraphs",
      "parallel edges",
      "edges cross",
      "logarithmic factor",
      "consequence"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}