co.combinatorics - Undecidable graph problems?

From a MathSciNet search:

---

Földes, Stéphane; Steinberg, Richard
A topological space for which graph embeddability is undecidable.
J. Combin. Theory Ser. B 29 (1980), no. 3, 342--344.

From the introduction: ``From Edmonds' permutation theorem and a generalization due to Stahl, it follows that graph embeddability is decidable for all surfaces, orientable as well as nonorientable. We show the existence of a topological space $hat G$ such that there is no algorithm to decide whether a finite graph is embeddable in $hat G$. In fact, $hat G$ will be a path-connected subspace of the real plane.''

---