Минимизация изгиба
В стилях рисования графов которые представляют ребра графа , полилиниями соединенных (последовательностью отрезков линий, в изгибах ), желательно минимизировать количество изгибов на одно ребро (иногда называемое сложностью кривой ). [1] или общее количество изгибов на чертеже. [2] Минимизация изгибов — это алгоритмическая задача поиска чертежа, минимизирующего эти величины. [3] [4]
Устранение всех изгибов
[ редактировать ]Прототипическим примером минимизации изгибов является теорема Фари , которая утверждает, что каждый плоский граф можно нарисовать без изгибов, то есть со всеми его ребрами, нарисованными как отрезки прямых линий. [5]
Рисунки графа, в которых ребра не изогнуты и выровнены по осям, иногда называют прямолинейными рисунками и являются одним из способов построения рисунков RAC , в которых все пересечения находятся под прямым углом. [6] Однако NP-полно определить, имеет ли плоский граф плоский прямолинейный рисунок: [7] и NP-полный, чтобы определить, имеет ли произвольный граф прямолинейный рисунок, допускающий пересечения. [6]
Минимизация изгиба
[ редактировать ]Тамассиа (1987) показал, что минимизация изгиба ортогональных рисунков плоских графов, в которых вершины размещены в целочисленной решетке , а ребра нарисованы как ломаные линии, выровненные по осям, может быть выполнена за полиномиальное время путем перевода задачи в одну из минимальных -стоимость сетевого потока . [8] [9] Однако если плоское вложение графа можно изменить, то минимизация изгиба становится NP-полной и вместо этого должна решаться с помощью таких методов, как целочисленное программирование , которые не гарантируют как быстрое время выполнения, так и точный ответ. [10]
Несколько изгибов на край
[ редактировать ]Многие стили рисования графов допускают изгибы, но только ограниченным образом: сложность кривых этих рисунков (максимальное количество изгибов на ребро) ограничена некоторой фиксированной константой. Разрешение этой константе увеличиваться можно использовать для улучшения других аспектов рисунка, например его площади . [1] Альтернативно, в некоторых случаях стиль рисования может быть возможен только в том случае, если разрешены изгибы; например, не каждый граф имеет рисунок RAC (рисунок со всеми пересечениями под прямым углом) без изгибов или со сложностью кривой два, но в каждом графе есть такой рисунок со сложностью кривой три. [11]
Ссылки
[ редактировать ]- ^ Jump up to: а б Ди Джакомо, Эмилио; Дидимо, Уолтер; Лиотта, Джузеппе; Мейер, Хенк (2011), «Площадь, сложность кривой и разрешение пересечений неплоских графических рисунков», Theory of Computing Systems , 49 (3): 565–575, doi : 10.1007/s00224-010-9275-6 , МР 2822838 .
- ^ Баттиста, Джузеппе; Идс, Питер ; Тамассия, Роберт ; Толлис, Иоаннис Г. (1998), Рисование графиков: алгоритмы визуализации графиков (1-е изд.), Prentice Hall, стр. 15–16, ISBN 978-0133016154 .
- ^ Ди Баттиста и др. (1998) , с. 145.
- ^ Покупка, Хелен (1997), «Какая эстетика оказывает наибольшее влияние на человеческое понимание?», Рисунок графика: 5-й Международный симпозиум, GD '97, Рим, Италия, 18–20 сентября 1997 г., Труды , Конспекты лекций по информатике , том . 1353, стр. 248–261, номер документа : 10.1007/3-540-63938-1_67 , ISBN. 978-3-540-63938-1 .
- ^ Ди Баттиста и др. (1998) , с. 140.
- ^ Jump up to: а б Идс, Питер ; Хонг, Сок Хи ; Пун, Шеунг-Хунг (2010), «О прямолинейном рисовании графиков», Рисование графиков: 17-й Международный симпозиум, GD 2009, Чикаго, Иллинойс, США, 22–25 сентября 2009 г., Переработанные статьи , Конспекты лекций по информатике, том . 5849, Springer, стр. 232–243, номер doi : 10.1007/978-3-642-11805-0_23 , ISBN. 978-3-642-11804-3 , МР 2680455 .
- ^ Гарг, Ашим; Тамассиа, Роберто (2001), «О вычислительной сложности тестирования восходящей и прямолинейной планарности», SIAM Journal on Computing , 31 (2): 601–625, doi : 10.1137/S0097539794277123 , MR 1861292 .
- ^ Тамассиа, Роберто (1987), «О встраивании графа в сетку с минимальным количеством изгибов», SIAM Journal on Computing , 16 (3): 421–444, doi : 10.1137/0216030 , MR 0889400 .
- ^ Корнельсен, Сабина; Карренбауэр, Андреас (2012), «Минимизация ускоренного изгиба», Журнал графовых алгоритмов и приложений , 16 (3): 635–650, doi : 10.7155/jgaa.00265 , MR 2983428 .
- ^ Мюцель, Петра ; Вейскирхер, Рене (2002), «Минимизация изгиба в ортогональных чертежах с использованием целочисленного программирования», Вычисления и комбинаторика: 8-я ежегодная международная конференция, COCOON 2002, Сингапур, 15–17 августа 2002 г., Труды , Конспекты лекций по информатике, том. 2387, стр. 484–493, CiteSeerX 10.1.1.138.1513 , doi : 10.1007/3-540-45655-4_52 , ISBN 978-3-540-43996-7 .
- ^ Дидимо, Уолтер; Идс, Питер ; Лиотта, Джузеппе (2009), «Рисование графиков с пересечениями под прямым углом», Алгоритмы и структуры данных: 11-й международный симпозиум, WADS 2009, Банф, Канада, 21–23 августа 2009 г. Труды , конспекты лекций по информатике, том. 5664, стр. 206–217, номер документа : 10.1007/978-3-642-03367-4_19 , ISBN. 978-3-642-03366-7 .