Минимизация изгиба
Графическое изображение с небольшим количеством изгибов краев

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

Устранение всех изгибов

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

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

Минимизация изгиба

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

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

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

Ссылки

  1. ^ ab Di Giacomo, Emilio; Didimo, Walter; Liotta, Giuseppe; Meijer, Henk (2011), "Площадь, сложность кривой и разрешение пересечения непланарных графовых рисунков", Теория вычислительных систем , 49 (3): 565– 575, doi :10.1007/s00224-010-9275-6, MR  2822838.
  2. ^ Ди Баттиста, Джузеппе; Идс, Питер ; Тамассиа, Роберто ; Толлис, Иоаннис Г. (1998), Рисование графов: алгоритмы визуализации графов (1-е изд.), Prentice Hall, стр.  15–16 , ISBN 978-0133016154.
  3. ^ Ди Баттиста и др. (1998), с. 145.
  4. ^ Перчейз, Хелен (1997), «Какая эстетика оказывает наибольшее влияние на человеческое понимание?», Графическое рисование: 5-й Международный симпозиум, GD '97 Рим, Италия, 18–20 сентября 1997 г., Труды , Заметки лекций по информатике , т. 1353, стр.  248–261 , doi : 10.1007/3-540-63938-1_67 , ISBN 978-3-540-63938-1.
  5. ^ Ди Баттиста и др. (1998), с. 140.
  6. ^ ab Eades, Peter ; Hong, Seok-Hee ; Poon, Sheung-Hung (2010), "On rectilinear drawing of graphs", Graph Drawing: 17th International Symposium, GD 2009, Chicago, IL, USA, September 22-25, 2009, Revised Papers , Lecture Notes in Computer Science, vol. 5849, Springer, pp.  232–243 , doi : 10.1007/978-3-642-11805-0_23 , ISBN 978-3-642-11804-3, МР  2680455.
  7. ^ Гарг, Ашим; Тамассиа, Роберто (2001), «О вычислительной сложности тестирования восходящей и прямолинейной планарности», SIAM Journal on Computing , 31 (2): 601– 625, doi :10.1137/S0097539794277123, MR  1861292.
  8. ^ Тамассиа, Роберто (1987), «О встраивании графа в сетку с минимальным числом изгибов», SIAM Journal on Computing , 16 (3): 421– 444, doi :10.1137/0216030, MR  0889400.
  9. ^ Корнельсен, Сабина; Карренбауэр, Андреас (2012), «Ускоренная минимизация изгибов», Журнал графовых алгоритмов и приложений , 16 (3): 635–650 , doi : 10.7155/jgaa.00265 , MR  2983428.
  10. ^ Mutzel, Petra ; Weiskircher, René (2002), "Минимизация изгибов в ортогональных чертежах с использованием целочисленного программирования", Computing and Combinatorics: 8th Annual International Conference, COCOON 2002, Singapore, August 15–17, 2002, Proceedings , Lecture Notes in Computer Science, vol. 2387, pp.  484–493 , CiteSeerX 10.1.1.138.1513 , doi :10.1007/3-540-45655-4_52, ISBN  978-3-540-43996-7.
  11. ^ Дидимо, Уолтер; Идс, Питер ; Лиотта, Джузеппе (2009), «Рисование графов с прямыми угловыми пересечениями», Алгоритмы и структуры данных: 11-й международный симпозиум, WADS 2009, Банф, Канада, 21-23 августа 2009 г. Труды , Конспект лекций по информатике, т. 5664, стр.  206–217 , doi :10.1007/978-3-642-03367-4_19, ISBN 978-3-642-03366-7.
Взято с "https://en.wikipedia.org/w/index.php?title=Bend_minimization&oldid=1234807944"