Алгоритм рисования графов без проверки всех пар вершин?

Алгоритмы рисования графиков, такие как описанные здесь, проверьте все вершины два на два и применить дополнительные силы, если две вершины соединены ребром. Если у нас очень большой граф, проверка всех пар вершин будет дорогостоящей. Есть ли какой-либо алгоритм рисования графа, который рисует большой граф, используя только существующие ребра, а не проверяя все возможные пары?

РЕДАКТИРОВАТЬ
Под алгоритмом рисования я имел в виду алгоритм, который назначает положение в 2D или 3D каждой вершине таким образом, чтобы рендеринг сфер или кругов (или любой другой формы) в качестве вершин в назначенных им положениях приводил к правдоподобное визуальное представление всего графика.


graph algorithm graph-algorithm graph-drawing
person Farzad    schedule 08.01.2014    source источник
comment
граф должен быть плоским?   -  person Tomas    schedule 11.01.2014
comment
Проблема с вашим вопросом заключается в очень неясных требованиях к алгоритму рисования - правдоподобное визуальное представление не является четким объективным критерием. Я могу легко создать для вас очень простой алгоритм рисования, который будет соответствовать условию, но будет создавать уродливые графики. Кто будет решать, что некрасиво, а что нет?   -  person Tomas    schedule 11.01.2014
comment
Я думал, что в литературе должен быть алгоритм, удовлетворяющий упомянутым условиям.   -  person Farzad    schedule 11.01.2014
comment
Какие условия? Вы не указали четких условий. Вернитесь и прочтите мой предыдущий комментарий еще раз.   -  person Tomas    schedule 11.01.2014
comment
Условия, в которых алгоритм выполняет рисунок. Я ищу ранее предложенный алгоритм, который не должен выполнять вычисление 2 на 2 для всех вершин в графе.   -  person Farzad    schedule 11.01.2014
comment
Хорошо, тогда просто присвойте координаты [0, 0] каждой вершине. Это алгоритм рисования, который соответствует вашим условиям.   -  person Tomas    schedule 11.01.2014
comment
См. Описание по ссылке в ответе. Это объясняет, чего я хотел. Мне очень жаль, если я не смог должным образом передать эту идею в своей голове.   -  person Farzad    schedule 15.01.2014

Ответы (2)


arrow_upward
0
arrow_downward

Проверьте это Spring-Electrical Embedding. Оно находится в O (nlog n).

person Peng Zhang    schedule 15.01.2014
comment
Спасибо. Это то, о чем я думал как о решении: ограничить силу притяжения ближайшими вершинами. Я думаю, что это увеличивает накладные расходы на знание соседей, но это не то, что нельзя решить. - person Farzad; 15.01.2014
comment
Пэн, что такое n? Вы всегда должны говорить, что такое n, если вы ставите такое выражение. Верно @ Фарзад? - person Tomas; 15.01.2014
comment
@Tomas, n - количество узлов в графе. Это общепринятое обозначение теории графов. :-) - person Peng Zhang; 15.01.2014
comment
Что ж, тогда это явно неверно, потому что количество ребер может быть до n (n-1) / 2. Как вы хотите нарисовать O(n^2) ребро за O(n log n) время? - person Tomas; 15.01.2014
comment
И, кстати, такие ответы не приветствуются, потому что они не содержат ничего, кроме ссылки, которая может перестать работать. - person Tomas; 15.01.2014
comment
@Tomas то, о чем вы говорите, - это худший случай, которого не бывает для реальных больших графиков. Взгляните на набор данных большого графа SNAP. Эти большие графы разрежены, они могут иметь миллионы вершин, но не иметь сотен миллиардов ребер. Плюс в этом посте есть ответ, который я искал. Полезная ссылка лучше длинного бесполезного ответа или отсутствия ответа. - person Farzad; 15.01.2014

arrow_upward
0
arrow_downward

Если у вас разреженная матрица, вы можете подумать о создании графа в виде списка соседей или более простого, например, пары вершин (например, (1, 3) и 1 и 3 - это количество вершин).

person upstreamfall    schedule 08.01.2014
comment
Наличие списка ребер - это формат представления и хранения, а не формат рисования графа. Редактирую вопрос и добавляю это. - person Farzad; 08.01.2014