Today I read a paper titled “The problem of compatible representatives”
The abstract is:
The purpose of this note is to attach a name to a natural class of combinatorial problems and to point out that this class includes many important special cases.
We also show that a simple problem of placing nonoverlapping labels on a rectangular map is NP-complete..