Выпуклый рисунок - Convex drawing

Выпуклые и строго выпуклые сеточные чертежи одного и того же графа

В рисунок графика, а выпуклый рисунок из планарный граф - рисунок, на котором вершины графа изображены в виде точек Евклидова плоскость и края как отрезки прямых линий таким образом, что все грани чертежа (включая внешнюю грань) имеют выпуклую границу. Граница грани может проходить прямо через одну из вершин графа, не поворачиваясь; а строго выпуклый рисунок дополнительно просит, чтобы граница грани поворачивалась в каждой вершине. То есть на строго выпуклом чертеже каждая вершина графа также является вершиной каждого выпуклого многоугольника, описывающего форму каждой падающей грани.

Каждые многогранный граф имеет строго выпуклый рисунок,[1] например, полученный как Диаграмма Шлегеля из выпуклый многогранник представляющий граф. Для этих графов выпуклый (но не обязательно строго выпуклый) рисунок может быть найден в сетке, длина которой с каждой стороны линейна по количеству вершин графа за линейное время.[2][3] Однако для строго выпуклых чертежей могут потребоваться сетки большего размера; например, для любого многогранника, такого как пирамида в которой одна грань имеет линейное число вершин, для строго выпуклого изображения ее графа требуется сетка кубической площади.[4] Алгоритм линейного времени может находить строго выпуклые рисунки многогранных графов в сетке, длина каждой стороны которой квадратична.[5]

Выпуклый, но не строго выпуклый рисунок полный двудольный граф

Другие графы, не являющиеся многогранными, также могут иметь выпуклые или строго выпуклые рисунки. Некоторые графики, такие как полный двудольный граф , имеют выпуклые рисунки, но не строго выпуклые. Известна комбинаторная характеристика графов с выпуклыми рисунками:[6] и их можно распознать за линейное время,[7] но размеры сетки, необходимые для их чертежей, и эффективный алгоритм построения небольших выпуклых сеточных чертежей этих графов известны не во всех случаях.[8]

Выпуклые рисунки следует отличать от выпуклые вложения, в котором каждая вершина должна лежать в пределах выпуклый корпус соседних вершин. Выпуклые вложения могут существовать в измерениях, отличных от двух, не требуют, чтобы их граф был плоским, и даже для плоских вложений планарных графов не обязательно заставляют внешнюю грань быть выпуклой.[9]

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

  1. ^ Тутте, В. Т. (1960), «Выпуклые представления графов», Труды Лондонского математического общества, Третья серия, 10: 304–320, Дои:10.1112 / плмс / с3-10.1.304, Г-Н  0114774
  2. ^ Кант, Г. (1996), "Рисование плоских графов с использованием канонического порядка", Алгоритмика, 16 (1): 4–32, Дои:10.1007 / s004539900035, HDL:1874/16676, Г-Н  1394492
  3. ^ Бонишон, Николас; Фельснер, Стефан; Мосбах, Мохамед (2007), "Выпуклые рисунки 3-связных плоских графов", Алгоритмика, 47 (4): 399–420, Дои:10.1007 / s00453-006-0177-6, Г-Н  2304987, S2CID  375595
  4. ^ Эндрюс, Джордж Э. (1963), "Нижняя оценка объема строго выпуклых тел со многими точками граничной решетки", Труды Американского математического общества, 106 (2): 270–279, Дои:10.2307/1993769, JSTOR  1993769, Г-Н  0143105
  5. ^ Барань, Имре; Роте, Гюнтер (2006), "Строго выпуклые рисунки плоских графов", Documenta Mathematica, 11: 369–391, arXiv:cs / 0507030, Г-Н  2262937
  6. ^ Томассен, Карстен (1980), "Планарность и двойственность конечных и бесконечных графов", Журнал комбинаторной теории, Серия B, 29 (2): 244–271, Дои:10.1016/0095-8956(80)90083-0, Г-Н  0586436
  7. ^ Чиба, Норишиге; Яманучи, Тадаши; Нишизеки, Такао (1984), «Линейные алгоритмы для выпуклых чертежей плоских графов», в Бонди, Дж. Адриан; Мурти, США (ред.), Прогресс в теории графов (Waterloo, Ont., 1982), Academic Press, стр. 153–173, Г-Н  0776799
  8. ^ Чжоу, Сяо; Нишизеки, Такао (2010), «Выпуклые рисунки внутренне трехсвязных плоских графов на сетки », Дискретная математика, алгоритмы и приложения, 2 (3): 347–362, Дои:10.1142 / S179383091000070X, Г-Н  2728831
  9. ^ Линиал, Н.; Ловас, Л.; Вигдерсон, А. (1988), "Резинки, выпуклые вложения и связность графов", Комбинаторика, 8 (1): 91–102, Дои:10.1007 / BF02122557, Г-Н  0951998, S2CID  6164458