{
  "id": "1802.10300",
  "version": "v1",
  "published": "2018-02-28T08:06:22.000Z",
  "updated": "2018-02-28T08:06:22.000Z",
  "title": "Edge Partitions of Optimal $2$-plane and $3$-plane Graphs",
  "authors": [
    "Michael Bekos",
    "Emilio Di Giacomo",
    "Walter Didimo",
    "Giuseppe Liotta",
    "Fabrizio Montecchiani",
    "Chrysanthi Raftopoulou"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "A topological graph is a graph drawn in the plane. A topological graph is $k$-plane, $k>0$, if each edge is crossed at most $k$ times. We study the problem of partitioning the edges of a $k$-plane graph such that each partite set forms a graph with a simpler structure. While this problem has been studied for $k=1$, we focus on optimal $2$-plane and $3$-plane graphs, which are $2$-plane and $3$-plane graphs with maximum~density. We prove the following results. (i) It is not possible to partition the edges of a simple optimal $2$-plane graph into a $1$-plane graph and a forest, while (ii) an edge partition formed by a $1$-plane graph and two plane forests always exists and can be computed in linear time. (iii) We describe efficient algorithms to partition the edges of a simple optimal $2$-plane graph into a $1$-plane graph and a plane graph with maximum vertex degree $12$, or with maximum vertex degree $8$ if the optimal $2$-plane graph is such that its crossing-free edges form a graph with no separating triangles. (iv) We exhibit an infinite family of simple optimal $2$-plane graphs such that in any edge partition composed of a $1$-plane graph and a plane graph, the plane graph has vertex degree at least $6$. (v) We show that every optimal $3$-plane graph whose crossing-free edges form a biconnected graph can be decomposed into a $2$-plane graph and two plane forests.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-02-28T08:06:22.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "plane graph",
      "edge partition",
      "maximum vertex degree",
      "crossing-free edges form",
      "simple optimal"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}