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.
精彩评论