开发者

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.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜