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

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

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

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

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

Ссылки

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

[tutte-1] Тутте, WT (1960), «Выпуклые представления графов», Труды Лондонского математического общества , третья серия, 10 : 304–320, doi : 10.1112/plms/s3-10.1.304 , MR 0114774

[kant-2] Кант, Г. (1996), «Рисование плоских графов с использованием канонического порядка», Algorithmica , 16 (1): 4–32, doi : 10.1007/s004539900035 , hdl : 1874/16676 , MR 1394492

[bfm-3] Боничон, Николя; Фельснер, Стефан; Мосбах, Мохамед (2007), «Выпуклые рисунки 3-связных плоских графов», Algorithmica , 47 (4): 399–420, doi : 10.1007/s00453-006-0177-6 , MR 2304987 , S2CID 375595

[andrews-4] Эндрюс, Джордж Э. (1963), «Нижняя оценка объема строго выпуклых тел со многими граничными точками решетки», Transactions of the American Mathematical Society , 106 (2): 270–279, doi : 10.2307/1993769 , JSTOR 1993769 , МР 0143105

[br-5] Барань, Имре ; Роте, Гюнтер (2006), «Строго выпуклые рисунки плоских графов», Documenta Mathematica , 11 : 369–391, arXiv : cs/0507030 , doi : 10.4171/dm/214 , MR 2262937 , S2CID 47071207

[thomassen-6] Томассен, Карстен (1980), «Планарность и двойственность конечных и бесконечных графов», Журнал комбинаторной теории , серия B, 29 (2): 244–271, doi : 10.1016/0095-8956(80)90083-0 , MR 0586436

[cyn-7] Тиба, Норисигэ; Яманучи, Тадаши; Нишизеки, Такао (1984), «Линейные алгоритмы для выпуклых рисунков плоских графов», Бонди, Дж. Адриан; Мерти, USR (ред.), Прогресс в теории графов (Ватерлоо, Онтарио, 1982) , Academic Press, стр. 153–173, MR 0776799

[zn-8] Чжоу, Сяо; Нишизеки, Такао (2010), «Выпуклые рисунки внутренне трехсвязных плоских графов на $O(n^{2})$ сетки», «Дискретная математика, алгоритмы и приложения» , 2 (3): 347–362, doi : 10.1142/S179383091000070X , MR 2728831

[llw-9] Линиал, Н. ; Ловас, Л. ; Вигдерсон, А. (1988), «Резиновые ленты, выпуклые вложения и связность графов», Combinatorica , 8 (1): 91–102, doi : 10.1007/BF02122557 , MR 0951998 , S2CID 6164458

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]