DRAKON.SU

Текущее время: Четверг, 24 Сентябрь, 2020 15:38

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ 1 сообщение ] 
Автор Сообщение
СообщениеДобавлено: Понедельник, 14 Октябрь, 2019 23:08 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 4842
Откуда: Москва
Язык ДРАКОН
и минимизация изломов ребер графа


http://bit.ly/2McAFCe

Цитата:
Минимизация изломов

Материал из Википедии — свободной энциклопедии

При визуализации графов, когда рёбра графа представляются ломаными (последовательностью отрезков, соединённых в точках излома), желательно минимизировать число изломов на ребро (что иногда называется сложностью кривой)[1] или общее число изломов на рисунке[2].

Минимизация изломов — это алгоритмическая задача поиска рисунка графа, минимизирующего указанные величины[3][4].


Содержание

1 Исключение изломов
2 Минимизация изломов
3 Несколько изломов на ребро
4 Примечания
5 Литература

Исключение изломов

Классическим примером минимизации изломов служит теорема Фари, утверждающая, что любой планарный граф можно нарисовать без изломов, то есть можно найти планарное вложение графа, в котором все рёбра будут представлены отрезками[5].

Представление графа, в котором рёбра не имеют изломов и параллельны осям, иногда называется прямоугольным представлением и является одним из вариантов представления с ортогональным пересечением рёбер[en], в котором все пересечения рёбер происходят под прямым углом[6].

Однако определение, имеет ли планарный граф прямоугольное преставление, является NP-полной задачей[7].

NP-полной задачей является также определение, имеет ли произвольный граф прямоугольное представление при допущении пересечений рёбер[6].

Минимизация изломов

Тамассиа показал, что минимизация изломов ортогонального рисунка планарных графов, в котором вершины размещаются в узлах целочисленной решётки а рёбра рисуются в виде ломаных, состоящих из отрезков, параллельных осям, может быть осуществлена за полиномиальное время путём перевода задачи в задачу поиска потока минимальной стоимости[8][9].

Однако если изменить способ вложения планарного графа, задача минимизации изломов становится NP-полной и должна решаться методами, такими как целочисленное программирование, которое не гарантирует одновременность получения точного решения и быстрой скорости работы[10].

Несколько изломов на ребро

Многие стили рисования графов позволяют изломы, но в ограниченном виде — сложность кривой этих представлений (максимальное число изломов на одно ребро) ограничивается некоторой константой. Разрешение этой константе подрасти может быть использовано для улучшения других характеристик рисунка, таких как площадь[1].

В некоторых случаях стиль может оказаться возможным только при разрешении изломов. Например, не всякий граф имеет представление с ортогональным пересечением рёбер[en] без изломов, или со сложностью кривой два, но любой граф имеет такой рисунок со сложностью кривой три[11].

Примечания

Di Giacomo, Didimo, Liotta, Meijer, 2011, с. 565–575.
Di Battista, Eades, Tamassia, Tollis, 1998, с. 15–16.
Di Battista, Eades, Tamassia, Tollis, 1998, с. 145.
Purchase, 1997, с. 248–261.
Di Battista, Eades, Tamassia, Tollis, 1998, с. 140.
Eades, Hong, Poon, 2010, с. 232–243.
Garg, Tamassia, 2001, с. 601–625.
Tamassia, 1987, с. 421–444.
Cornelsen, Karrenbauer, 2012, с. 635–650.
Mutzel, Weiskircher, 2002, с. 484–493.
Didimo, Eades, Liotta, 2009, с. 206–217.

Литература

Emilio Di Giacomo, Walter Didimo, Giuseppe Liotta, Henk Meijer. Area, curve complexity, and crossing resolution of non-planar graph drawings // Theory of Computing Systems. — 2011. — Т. 49, вып. 3. — С. 565–575. — DOI:10.1007/s00224-010-9275-6.
Giuseppe Di Battista, Peter Eades, Roberto Tamassia, Ioannis G. Tollis. Graph Drawing: Algorithms for the Visualization of Graphs. — 1st. — Prentice Hall, 1998. — С. 15–16. — ISBN 0133016153.
Helen Purchase. Which aesthetic has the greatest effect on human understanding? // Graph Drawing: 5th International Symposium, GD '97 Rome, Italy, September 18–20, 1997, Proceedings. — 1997. — Т. 1353. — С. 248–261. — (Lecture Notes in Computer Science). — DOI:10.1007/3-540-63938-1_67.
Ashim Garg, Roberto Tamassia. On the computational complexity of upward and rectilinear planarity testing // SIAM Journal on Computing. — 2001. — Т. 31, вып. 2. — С. 601–625. — DOI:10.1137/S0097539794277123.
Peter Eades, Seok-Hee Hong, Sheung-Hung Poon. On rectilinear drawing of graphs // Graph Drawing: 17th International Symposium, GD 2009, Chicago, IL, USA, September 22-25, 2009, Revised Papers. — Springer, 2010. — Т. 5849. — С. 232–243. — (Lecture Notes in Computer Science). — DOI:10.1007/978-3-642-11805-0_23.
Roberto Tamassia. On embedding a graph in the grid with the minimum number of bends // SIAM Journal on Computing. — 1987. — Т. 16, вып. 3. — С. 421–444. — DOI:10.1137/0216030.
Sabine Cornelsen, Andreas Karrenbauer. Accelerated bend minimization // Journal of Graph Algorithms and Applications. — 2012. — Т. 16, вып. 3. — С. 635–650. — DOI:10.7155/jgaa.00265.
Petra Mutzel, René Weiskircher. Bend minimization in orthogonal drawings using integer programming // Computing and Combinatorics: 8th Annual International Conference, COCOON 2002, Singapore, August 15–17, 2002, Proceedings. — 2002. — Т. 2387. — С. 484–493. — (Lecture Notes in Computer Science). — DOI:10.1007/3-540-45655-4_52.
Walter Didimo, Peter Eades, Giuseppe Liotta. Drawing graphs with right angle crossings // Algorithms and Data Structures: 11th International Symposium, WADS 2009, Banff, Canada, August 21-23, 2009. Proceedings. — 2009. — Т. 5664. — С. 206–217. — (Lecture Notes in Computer Science). — DOI:10.1007/978-3-642-03367-4_19.


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ 1 сообщение ] 

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 2


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2008-2020, участники конференции «DRAKON.SU», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB