{
  "id": "2309.06507",
  "version": "v1",
  "published": "2023-09-12T18:23:36.000Z",
  "updated": "2023-09-12T18:23:36.000Z",
  "title": "The maximum size of adjacency-crossing graphs",
  "authors": [
    "Eyal Ackerman",
    "Balázs Keszegh"
  ],
  "comment": "17 pages, 11 figures",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "An adjacency-crossing graph is a graph that can be drawn such that every two edges that cross the same edge share a common endpoint. We show that the number of edges in an $n$-vertex adjacency-crossing graph is at most $5n-10$. If we require the edges to be drawn as straight-line segments, then this upper bound becomes $5n-11$. Both of these bounds are tight. The former result also follows from a very recent and independent work of Cheong et al.\\cite{cheong2023weakly} who showed that the maximum size of weakly and strongly fan-planar graphs coincide. By combining this result with the bound of Kaufmann and Ueckerdt\\cite{KU22} on the size of strongly fan-planar graphs and results of Brandenburg\\cite{Br20} by which the maximum size of adjacency-crossing graphs equals the maximum size of fan-crossing graphs which in turn equals the maximum size of weakly fan-planar graphs, one obtains the same bound on the size of adjacency-crossing graphs. However, the proof presented here is different, simpler and direct.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-09-12T18:23:36.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "68R10",
      "05C10"
    ],
    "keywords": [
      "maximum size",
      "strongly fan-planar graphs coincide",
      "edge share",
      "upper bound",
      "independent work"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 17,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}