Planar 3DM is NP-complete. (English) Zbl 0606.68065
A restriction of the three-dimensional matching problem 3DM, in which the associated bipartite graph is planar, is shown to remain NP-complete. The restriction is inspired by that of D. Lichtenstein’s planar 3SAT [SIAM J. Comput. 11, 329-343 (1982; Zbl 0478.68043)]. Like Planar 3SAT, Planar 3DM is principally a tool for use in NP-completeness proofs for planar restrictions of other problems. Several examples of its applications in this respect are given.
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 68Q25 | Analysis of algorithms and problem complexity |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
