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

Перейти к навигацииПерейти к поиску

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

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

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

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

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

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

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

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

Примечания

  1. ↑ 1 2 Di Giacomo, Didimo, Liotta, Meijer, 2011, с. 565–575.
  2. ↑ Di Battista, Eades, Tamassia, Tollis, 1998, с. 15–16.
  3. ↑ Di Battista, Eades, Tamassia, Tollis, 1998, с. 145.
  4. ↑ Purchase, 1997, с. 248–261.
  5. ↑ Di Battista, Eades, Tamassia, Tollis, 1998, с. 140.
  6. ↑ 1 2 Eades, Hong, Poon, 2010, с. 232–243.
  7. ↑ Garg, Tamassia, 2001, с. 601–625.
  8. ↑ Tamassia, 1987, с. 421–444.
  9. ↑ Cornelsen, Karrenbauer, 2012, с. 635–650.
  10. ↑ Mutzel, Weiskircher, 2002, с. 484–493.
  11. ↑ 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.