Описание тега planar-graph

Описание тега Вопросы с тегом
В теории графов планарный граф - это граф, который можно вложить в плоскость без пересечений ребер.
0 ответов

Как найти "контур" (вогнутого) графа в 2D плоскости?

У меня есть связный граф в 2D плоскости, состоящей из нескольких вершин и некоторых ребер, определенных между ними. Общая форма графа не обязательно является выпуклой, то есть смежные вершины выпуклой оболочки не всегда связаны ребром. Есть ли сущес…
07 авг '15 в 20:52
2 ответа

Алгоритм построения простого графа

Я хочу знать, есть ли какой-нибудь алгоритм, который превращает граф в планарный граф? Я искал в Google, я не нашел то, что может мне помочь
02 янв '14 в 20:35
1 ответ

Минимизируйте перекрестные края на графике

Я использую networkx (пакет для рисования графов на python) http://networkx.lanl.gov/index.html для одного из моих проектов. Хотя networkx довольно крутой, функция отображения отстой из-за количества поперечных граней. Есть ли способ минимизировать …
20 фев '11 в 16:10
0 ответов

Плоское вложение для неплоских графов в Boost Graph Library?

Похоже, что в библиотеке форсированных графов реализованы алгоритмы плоского вложения для максимально плоских графов. Есть ли в ней что-то реализованное для планаризации непланарного графа? Надеюсь, что-то, что минимизирует пересечения. Я обнаружил,…
29 сен '14 в 16:04
2 ответа

Реализации планарных графов / карт (с вложениями)

Для целей данного поста под плоским графом или плоской картой я буду подразумевать абстрактный граф, который можно нарисовать на плоскости (или эквивалентно на сфере) вместе с круговым порядком ребер в каждой вершине в соответствии с к конкретному т…
30 мар '13 в 16:56
1 ответ

Нарисуйте комбинаторное вложение общего плоского графа

У меня есть комбинаторное вложение общего плоского графа (вершины, ребра, циклическое упорядочение ребер вокруг вершин и внешней грани), и мне нужно его нарисовать. Вершины должны быть многомерными, и чертеж должен соответствовать определенному цикл…
26 июн '13 в 16:17
1 ответ

Соединить четное количество узлов без пересечения

У меня есть два набора из n узлов. Теперь я хочу соединить каждый узел из одного набора с другим узлом из другого набора. Полученный граф не должен иметь пересечений. Я знаю несколько алгоритмов линии развертки (алгоритм Бентли-Оттмана, чтобы провер…
29 июн '16 в 08:53
1 ответ

Планарность графика с фиксированными позициями узлов

У меня есть неориентированный граф с фиксированными позициями узлов. Узлы не могут быть перемещены, объединены, удалены или иным образом изменены. Края прикреплены к своим узлам, но не обязательно должны быть прямыми. Мне нужно знать, можно ли "согн…
25 май '16 в 12:17
0 ответов

Создание двойственного графа - обход плоской грани - vtkBoostGraphAdapter

Я пытаюсь написать алгоритм, который создает дуал графа. Чтобы проверить, является ли график плоским или нет, я использую тест плоскостности Бойера-Мирволда (реализация Boost) через vtkBoostGraphAdapter, Это прекрасно работает (только на vtkUndirect…
12 окт '14 в 20:25
1 ответ

Головоломка: Плоская конфигурация прямых соединительных линий

Головоломка: Учитывая четное количество точек в общих позициях на плоскости (то есть, нет трех точек, лежащих на одной линии), можете ли вы разделить точки на пары и соединить две точки каждой пары одной прямой линией так, чтобы прямая линии не пере…
25 май '14 в 19:41
2 ответа

Быстрый алгоритм для пересечения любых пересекающихся ребер в наборе многоугольников

У меня есть несколько полигонов, каждый из которых представлен в виде списка точек. Я ищу быстрый алгоритм, чтобы пройти список полигонов и пересечь все скрещенные ребра, пока не останется скрещенных ребер. Псудокод для текущей версии: While True: F…
04 янв '13 в 01:38
1 ответ

Тестирование графа плоскостности в R

Есть ли способ проверить, является ли сетевой граф плоским в R? Я смотрел в igraph, но безрезультатно. Я знаю, что могу с MATLAB, используя BGL toolbox, но я хочу знать, пробовал ли кто-нибудь это в R.
07 дек '16 в 13:51
4 ответа

Как проверить, является ли график плоским или нет?

Я изучаю планарный график и раскраску в C++. Но я не знаю, установить алгоритм, чтобы сделать эту работу. Кто-нибудь, пожалуйста, помогите мне? Здесь у меня есть некоторая информация для вас! Это мой код! И до сих пор функция не заканчивается. Если …
06 дек '09 в 08:06
2 ответа

Реализация алгоритма тестирования планарности

Я хочу написать алгоритм, который принимает в качестве входных данных граф и возвращает истину, если он плоский или ложь, если это не так. Я искал вокруг и нашел тонны алгоритмов, но нелегких для понимания реализаций. Есть ли какая-либо реализация, …
31 май '18 в 10:04
2 ответа

Самый быстрый алгоритм для планаризации графа

Я использую Processing для разработки навигационной системы для сложных данных и процессов. В рамках этого я довольно глубоко погрузился в макет графика. Это все забавно, и мои мнения об алгоритмах компоновки таковы: сила направлена ​​на бабу (прост…
18 ноя '11 в 13:32
1 ответ

Проверка на внешнюю планарность в графе с помощью BOOST?

Я просто концептуально хочу знать, как проверить, является ли график внешнепланарным или нет. Я знаю, что вы можете проверить планарность на графике с помощью BOOST, как вы проверяете внешнюю планарность? намеки?
27 ноя '14 в 15:04
0 ответов

Планарный граф из случайных точек

Я пытаюсь создать график с максимально возможным количеством прямых ребер между точками, не позволяя ни одному ребру пересекаться в Java. По сути, я пытаюсь построить планарный график со случайным количеством точек. Я в некоторой степени понимаю, ка…
02 мар '13 в 21:06
1 ответ

Java - создать диаграмму классов самостоятельно

Я работаю над небольшим проектом на Java, описанным ниже: Вход: список объектов для ориентированного графа. (Узлы с различными типами ребер: наследование, внутренний класс, классы друзей и т. Д.) Вывод: диаграмма классов, как можно более плоская. Мо…
02 сен '11 в 17:11
1 ответ

D3js избегать пересечений силового направления графа

Вот пример силового графа, который я пытался нарисовать с помощью d3.js. У меня 3 больших вопроса. И это код (вы можете запустить фрагмент кода ниже, он может работать): function getRandomInt(max, min = 0) { return Math.floor(Math.random() * (max - …
29 ноя '18 в 09:03
1 ответ

Как сертифицировать плоское вложение?

Я собираюсь реализовать алгоритм для вычисления плоского вложения. Я начал проверять свои результаты, запустив набор графиков (графы Рима) и сравнив свои результаты с результатами другой реализации (yfiles). Тем не менее, я могу только проверить, ра…
25 фев '14 в 11:58