Минимизация изгиба - Bend minimization

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

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

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

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

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

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

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

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

Рекомендации

  1. ^ а б Ди Джакомо, Эмилио; Дидимо, Уолтер; Лиотта, Джузеппе; Мейер, Хенк (2011), «Площадь, сложность кривой и разрешение пересечения неплоских графических чертежей», Теория вычислительных систем, 49 (3): 565–575, Дои:10.1007 / s00224-010-9275-6, МИСТЕР  2822838.
  2. ^ Ди Баттиста, Джузеппе; Идс, Питер; Тамассия, Роберто; Толлис, Иоаннис Г. (1998), Рисование графиков: алгоритмы визуализации графиков (1-е изд.), Прентис Холл, стр. 15–16, ISBN  978-0133016154.
  3. ^ Di Battista et al. (1998), п. 145.
  4. ^ Покупка, Елена (1997), «Какая эстетика оказывает наибольшее влияние на человеческое понимание?», Графический рисунок: 5-й Международный симпозиум, GD '97, Рим, Италия, 18–20 сентября 1997 г., Труды, Конспект лекций по информатике, 1353, стр. 248–261, Дои:10.1007/3-540-63938-1_67, ISBN  978-3-540-63938-1.
  5. ^ Di Battista et al. (1998), п. 140.
  6. ^ а б Идс, Питер; Хонг, Сок-Хи; Пун, Шеунг-Хунг (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.
  7. ^ Гарг, Ашим; Тамассия, Роберто (2001), «О вычислительной сложности тестирования восходящей и прямолинейной планарности», SIAM Журнал по вычислениям, 31 (2): 601–625, Дои:10.1137 / S0097539794277123, МИСТЕР  1861292.
  8. ^ Тамассия, Роберто (1987), «О вложении графа в сетку с минимальным числом изгибов», SIAM Журнал по вычислениям, 16 (3): 421–444, Дои:10.1137/0216030, МИСТЕР  0889400.
  9. ^ Корнельсен, Сабина; Карренбауэр, Андреас (2012), «Ускоренная минимизация изгиба», Журнал графических алгоритмов и приложений, 16 (3): 635–650, Дои:10.7155 / jgaa.00265, МИСТЕР  2983428.
  10. ^ Муцель, Петра; 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.
  11. ^ Дидимо, Уолтер; Идс, Питер; Лиотта, Джузеппе (2009), «Рисование графиков с пересечением под прямым углом», Алгоритмы и структуры данных: 11-й Международный симпозиум, WADS 2009, Банф, Канада, 21-23 августа 2009 г. Протоколы, Конспект лекций по информатике, 5664, стр. 206–217, Дои:10.1007/978-3-642-03367-4_19, ISBN  978-3-642-03366-7.