Graph planarization & drawing layout

[singalen]

Надо нам планаризовать и нарисовать в своём проекте ER-диаграмму.
Для этого её надо как минимум планаризовать.
Ну есть ещё граничные условия типа "9 несвязанных сущностей надо красиво выстаривать в шахматном порядке 3x3".
Жеплателен исходник на .NET под свободной лицензией типа LGPL.
Сваливаю сюда ссылки, которые нарыл, далее буду разбирать.
YFiles. Стоит, как самолёт: http://www.yworks.com/en/products_yfilesdotnet_commercialinfo_prices.htm
GOBLIN - много задач и layout: http://www.math.uni-augsburg.de/~fremuth/goblin.html#intro
GLEE - от MS: http://research.microsoft.com/users/levnach/GLEEWebPage.htm
Netron тоже от MS: http://www.orbifold.net/Netron/info.php
Симпозиум в Вене по теме рисования графов, см секцию Software Exhibition: http://www.informatik.uni-trier.de/~ley/db/conf/gd/gd2001.html
Каталог Open Source Graph Visualization in Java: http://www.manageability.org/blog/stuff/open-source-graph-network-visualization-in-java/view
Graphviz - крайне симпатично: http://www.graphviz.org/
upd: Отличный обзор библиотек.

Comments

[aleksijb.livejournal.com]

"Ну есть ещё граничные условия типа "9 несвязанных сущностей надо красиво выстаривать в шахматном порядке 3x3". "

Может, как вариант, побить граф на несвязанные компоненты? Потом каждую компоненту разбиваем на "слабосвязанные" компоненты. В результате получаем дерево компонент(например можно добавть возможность скрывать компоненты).
Первое что пришло в голову по поводу нахождения "слабозвязанных" компонент: если бы граф был сетью с истоком и стоком, то мы могли бы в сток залить скажем 1 литр и протолкнуть по графу. Дальше удаляем ребро с максимальным потоком. Опять проталиваем и удаляем, пока не разойдется на две несвязанные компоненты.

[singalen]

Та не в алгоритме ж дело :)
Вернее, не он главный. Главное - чтобы было красиво и вчера :)