Pondering this more constructively, and following up on Q1, it's plausible that we can restrict attention to triangulations of n-manifolds, since these have the least freedom to "flap around" during the embedding. And for the same reason, to minimal triangulations, such as the Csaszar (dual Szilassi) 7-point triangulation of the torus. Googling "minimal+triangulation+surface" turned up a nice page on this topic by Davide P. Cervone at http://www.math.union.edu/~dpvc/professional/research/traditional.html containing lots of surprising results --- I'm tempted to quote chunks, but the following must give the flavour: "For example, the real projective plane can be triangulated using only six vertices, but Brehm showed that it requires nine vertices to immerse this surface in three-space." [Hard to imagine the (equivalent) Steiner Roman surface requiring fewer than 10?] Fred Lunnon