| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4646583 | Discrete Mathematics | 2016 | 8 Pages |
Abstract
A graph GG is embeddable in RdRd if the vertices of GG can be assigned to points of RdRd in such a way that all pairs of adjacent vertices are at distance 1. We show that verifying embeddability of a given graph in RdRd is NP-hard in the case d>2d>2 for all reasonable notions of embeddability.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Mikhail Tikhomirov,