Putting graph on a grid

I have a directed graph with no loops with the following additional information:

• Every vertex has outdegree at most 4.
• Every edge is labeled 'up', 'right', 'down' or 'left'.
• If there is an 'up' edge from A to B, then there is a 'down' edge from B to A (i.e. it is symmetric).
• All edges which start at the same vertex have different labels.

I am looking for an algorithm that would assign 2d integer coordinates to each vertex, such tha开发者_StackOverflow社区t y(B) > y(A) whenever there is an 'up' edge from A to B, and similarly for other types of edges. Moreover, edges should not intersect.

For example, this is a picture of such a graph with 8 vertices:

1-------2---3
|           |
|   4       |
|   |       |
5---6---7---8

Note, that y(4) < y(1), since otherwise there would be intersecting edges.

I realize that the solution is far from unique, so one may require the result to have the minimal size in some sense.