Минимизация изгиба - Bend minimization
В рисунок графика стили, представляющие края из график к полилинии (последовательности отрезки линии подключен в изгибы) желательно минимизировать количество изгибов на кромку (иногда называемое сложность кривой)[1] или общее количество изгибов на чертеже.[2] Минимизация изгиба это алгоритмический проблема поиска чертежа, который минимизирует эти количества.[3][4]
Устранение всех изгибов
Прототипный пример минимизации изгиба: Теорема Фари, в котором говорится, что каждый планарный граф может быть нарисован без изгибов, то есть все его края нарисованы как отрезки прямых линий.[5]
Чертежи графа, в которых ребра не изгибаются и выровнены по осям, иногда называют прямолинейные рисунки, и являются одним из способов построения Чертежи RAC в котором все переходы расположены под прямым углом.[6] Однако это НП-полный определить, есть ли планарный граф имеет плоский прямолинейный рисунок,[7] и NP-complete, чтобы определить, имеет ли произвольный граф прямолинейный рисунок, допускающий пересечения.[6]
Минимизация изгиба
Тамасия (1987) показали, что минимизация изгиба ортогональные рисунки планарных графов, в которых вершины расположены в целочисленная решетка и края нарисованы как полилинии, выровненные по оси, могут быть выполнены в полиномиальное время переводя проблему в одну из минимальная стоимость сетевого потока.[8][9] Однако, если планарное вложение графа может быть изменено, тогда минимизация изгиба становится NP-полной и вместо этого должна решаться такими методами, как целочисленное программирование это не гарантирует как быстрого выполнения, так и точного ответа.[10]
Несколько изгибов на край
Многие стили рисования графиков допускают изгибы, но только ограниченным образом: сложность кривой этих чертежей (максимальное количество изгибов на кромку) ограничено некоторой фиксированной константой. Увеличение этой константы можно использовать для улучшения других аспектов чертежа, таких как площадь.[1] В качестве альтернативы, в некоторых случаях стиль рисования может быть возможен только тогда, когда разрешены изгибы; например, не каждый граф имеет Чертеж RAC (рисунок со всеми пересечениями под прямым углом) без изгибов или со сложностью кривой два, но на каждом графике есть такой рисунок со сложностью кривой три.[11]
Рекомендации
- ^ а б Ди Джакомо, Эмилио; Дидимо, Уолтер; Лиотта, Джузеппе; Мейер, Хенк (2011), «Площадь, сложность кривой и разрешение пересечения неплоских графических чертежей», Теория вычислительных систем, 49 (3): 565–575, Дои:10.1007 / s00224-010-9275-6, МИСТЕР 2822838.
- ^ Ди Баттиста, Джузеппе; Идс, Питер; Тамассия, Роберто; Толлис, Иоаннис Г. (1998), Рисование графиков: алгоритмы визуализации графиков (1-е изд.), Прентис Холл, стр. 15–16, ISBN 978-0133016154.
- ^ Di Battista et al. (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.
- ^ Di Battista et al. (1998), п. 140.
- ^ а б Идс, Питер; Хонг, Сок-Хи; Пун, Шеунг-Хунг (2010), «О прямолинейном рисовании графиков», Графический рисунок: 17-й Международный симпозиум, GD 2009, Чикаго, Иллинойс, США, 22-25 сентября 2009 г., Исправленные статьи, Конспект лекций по информатике, 5849, Springer, стр. 232–243, Дои:10.1007/978-3-642-11805-0_23, ISBN 978-3-642-11804-3, МИСТЕР 2680455.
- ^ Гарг, Ашим; Тамассия, Роберто (2001), «О вычислительной сложности тестирования восходящей и прямолинейной планарности», SIAM Журнал по вычислениям, 31 (2): 601–625, Дои:10.1137 / S0097539794277123, МИСТЕР 1861292.
- ^ Тамассия, Роберто (1987), «О вложении графа в сетку с минимальным числом изгибов», SIAM Журнал по вычислениям, 16 (3): 421–444, Дои:10.1137/0216030, МИСТЕР 0889400.
- ^ Корнельсен, Сабина; Карренбауэр, Андреас (2012), «Ускоренная минимизация изгиба», Журнал графических алгоритмов и приложений, 16 (3): 635–650, Дои:10.7155 / jgaa.00265, МИСТЕР 2983428.
- ^ Муцель, Петра; Weiskircher, René (2002), «Минимизация изгиба в ортогональных чертежах с использованием целочисленного программирования», Вычислительная техника и комбинаторика: 8-я ежегодная международная конференция, COCOON 2002, Сингапур, 15–17 августа 2002 г., Труды, Конспект лекций по информатике, 2387, стр. 484–493, CiteSeerX 10.1.1.138.1513, Дои: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.