Why use exactly that algorithm? It requires your graphs to be planar and 3-connected, which are quite restrictive requirements. Furthermore, the paper needs an outer face to be chosen for step 1, but it does not say how to determine that face. Usually you would need to first compute a planar embedding, then apply a heuristic to choose one of the faces as the outer face, see Gutwenger and Mutzel, "Graph Embedding with Minimum Depth and Maximum External Face" (http://www.springerlink.com/content/dbcv5uptvh1uyt92/).

On page 5 Plestenjak says for non-planar graphs you could choose an arbitrary vertex set to align on the outside, but I doubt you would get good results with that method. I would rather recommend to use the original algorithm of Fruchterman and Reingold, which is referenced by Plestenjak.

Thanks for your suggestion, i will discuss with my adviser.