Cách để ánh xạ biểu đồ tuần hoàn theo hướng tới lưới/ma trận

Question

Tôi có DAG với hàng nghìn đỉnh và cạnh.

Tôi đang tìm các thuật toán có thể định vị các đỉnh trên các điểm lưới theo cách thân thiện với con người/tính thẩm mỹ nhất. Linh cảm của tôi là bố trí đẹp nhất sẽ tương tự như bố cục với tổng độ dài cạnh tối thiểu.

Bạn có thể chỉ cho tôi các thuật toán hiệu quả cho số lượng tối thiểu các bố cục độ dài cạnh đó hoặc các thuật toán khác có thể giúp tôi giải quyết vấn đề này không?

Dưới đây là một phần của đầu ra từ một thuật toán rất ngây thơ:

Answer 1

Tôi khá chắc chắn đây là một vấn đề mở ("graph drawing"). Một vài điều khác mà bạn có thể muốn xem xét việc tối ưu hóa:

• góc giữa các cạnh xuất phát từ một đỉnh (tối đa)
• Số cửa cạnh (giảm thiểu)

Bạn có thể có thể sử dụng một thuật toán di truyền hoặc một số loại khác của metaheuristic, nhưng tôi không biết kết quả sẽ tốt như thế nào.