У меня есть ориентированный граф без петель со следующей дополнительной информацией:
- Каждая вершина имеет степень не более 4.
- Каждый край помечен как «вверх», «вправо», «вниз» или «влево».
- Если есть ребро «вверх» от А до В, то ребро «В» вниз от Б к А (то есть оно симметрично).
- Все ребра, начинающиеся в одной и той же вершине, имеют разные метки.
Я ищу алгоритм, который бы назначал 2d целочисленные координаты каждой вершине, чтобы y (B)> y (A) всякий раз, когда есть ребро «вверх» от A до B, и аналогично для ребер других типов , Более того, ребра не должны пересекаться.
Например, это изображение такого графа с 8 вершинами:
1-------2---3
| |
| 4 |
| | |
5---6---7---8
Обратите внимание, что y (4)
Я понимаю, что решение далеко не уникально, поэтому может потребоваться, чтобы результат в некотором смысле имел минимальный размер.