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