We present a general framework for computing various optimal embeddings of undirected and directed connected graphs in two and multi-dimensional integer lattices in time sub-exponential either in the minimum number n of lattice points used by such optimal embeddings or in the budget upper bound b on the number of lattice points that may be used in an embedding.

For the problem of minimum total edge length planar or multi-dimensional embedding or layout of a graph and the problem of an optimal protein folding in the so called HP model we obtain the upper bounds in terms of n. Note that in case of protein folding n is also the size of the input.

The list of problems for which we can derive the upper bounds in terms of b includes among other things:

- a minimum area planar embedding or layout of a graph,

- a minimum bend planar or three dimensional embedding or layout,

- a minimum maximum edge length planar or three dimensional

embedding or layout.

This is a joint work with Anders Dessmark and Eva−Marta Lundell.