Algorithm to find a polyhedral embedding
Doesn't this give you what you want?  Because you only care about the combinatorics, your problem is to embed a graph in a surface, I gather a surface of genus zero.


  Bojan Mohar, "Embedding graphs in an arbitrary surface in linear time," STOC 1996 (ACM link).