{
  "id": "1409.2426",
  "version": "v1",
  "published": "2014-09-08T16:49:45.000Z",
  "updated": "2014-09-08T16:49:45.000Z",
  "title": "Some NP-complete edge packing and partitioning problems in planar graphs",
  "authors": [
    "Jed Yang"
  ],
  "comment": "6 pages, 2 figures",
  "categories": [
    "math.CO",
    "cs.CC"
  ],
  "abstract": "Graph packing and partitioning problems have been studied in many contexts, including from the algorithmic complexity perspective. Consider the packing problem of determining whether a graph contains a spanning tree and a cycle that do not share edges. Bern\\'ath and Kir\\'aly proved that this decision problem is NP-complete and asked if the same result holds when restricting to planar graphs. Similarly, they showed that the packing problem with a spanning tree and a path between two distinguished vertices is NP-complete. They also established the NP-completeness of the partitioning problem of determining whether the edge set of a graph can be partitioned into a spanning tree and a (not-necessarily spanning) tree. We prove that all three problems remain NP-complete even when restricted to planar graphs.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-09-08T16:49:45.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "68Q17",
      "05C70",
      "68R10"
    ],
    "keywords": [
      "planar graphs",
      "partitioning problem",
      "np-complete edge packing",
      "spanning tree",
      "problems remain np-complete"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 6,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1409.2426Y"
    }
  }
}