Сглаживаемость графа

Уплощенность в некоторых $d$ -мерное нормированное векторное пространство — это свойство графов , которое гласит, что любое встраивание или рисование графа в некотором высоком измерении $d'$ можно «сгладить», чтобы жить в $d$ -размерности, такие, что расстояния между парами точек, соединенных ребрами, сохраняются. График $G$ является $d$ -сглаживается, если каждая система ограничения расстояния (DCS) с $G$ поскольку его граф ограничений имеет $d$ -мерный каркас . Уплощение сначала называлось реализуемостью. ^[1] но имя было изменено, чтобы избежать путаницы с графиком, имеющим некоторую DCS с $d$ -мерный каркас. ^[2]

Уплощение связано со структурной жесткостью , тенсегрити , конфигурационными пространствами Кэли и вариантом проблемы реализации графа .

Определения

Система ограничения расстояния $(G,\delta )$ , где $G=(V,E)$ это график и $\delta :E\rightarrow \mathbb {R} ^{|E|}$ — это задание расстояний на края $G$ , является $d$ -сглаживается в некотором нормированном векторном пространстве $\mathbb {R} ^{d}$ если существует структура $(G,\delta )$ в $d$ -размеры.

График $G=(V,E)$ является $d$ -сплющиваемый в $\mathbb {R} ^{d}$ если каждая система ограничений расстояния с $G$ поскольку его граф ограничений $d$ -сплющенный.

Уплощение также можно определить в терминах конфигурационных пространств Кэли; см. подключение к пространствам конфигурации Кэли ниже.

Характеристики

Замыкание по подграфам. Уплощаемость замкнута при взятии подграфов. ^[1] Чтобы убедиться в этом, заметим, что для некоторого графа $G$ , все возможные вложения подграфа $H$ из $G$ содержатся во множестве всех вложений $G$ .

Минор-закрытый. Уплощение — это свойство с малой замкнутостью по тому же аргументу, что и выше. ^[1]

Размер сглаживания. Размерность выравнивания графика $G$ в некотором нормированном векторном пространстве является наименьшим измерением $d$ такой, что $G$ является $d$ -сплющенный. Размерность сглаживания графа тесно связана с его граммовой размерностью. ^[3] Ниже приводится верхняя граница размерности уплощения произвольного графа при $l_{2}$ -норм.

Теорема. ^[4] Размерность выравнивания графика $G=\left(V,E\right)$ под $l_{2}$ -норма максимум $O\left({\sqrt {\left|E\right|}}\right)$ .

Подробное рассмотрение этой темы см. в главе 11.2 книги Deza & Laurent. ^[5]

Евклидова уплощаемость

В этом разделе рассматриваются результаты уплощения в евклидовом пространстве , где расстояние измеряется с помощью $l_{2}$ норма, также называемая евклидовой нормой .

1-сглаживаемые графы

Следующая теорема является фольклорной и показывает, что единственным запрещенным минором для 1-сглаживаемости является полный граф. $K_{3}$ .

Теорема. Граф является 1-сглаживаемым тогда и только тогда, когда он является лесом .

**Рисунок 1.** Двумерная структура РСУ, граф которой представляет собой дерево с шестью вершинами, показана синим цветом. Одномерный каркас той же DCS показан красным.

Доказательство. Доказательство можно найти в Belk & Connelly. ^[1] В одном направлении лес представляет собой набор деревьев, и любая система ограничений на расстояние, графом которой является дерево, может быть реализована в одномерном измерении. В другом направлении, если график $G$ не лес, то он имеет полный граф $K_{3}$ как подграф. Рассмотрим DCS, которая присваивает расстояние 1 краям $K_{4}$ подграф и расстояние 0 до всех остальных ребер. Эта DCS имеет реализацию в 2-мерном измерении как 1-скелет треугольника, но не имеет реализации в 1-мерном измерении.

Это доказательство допускало, что расстояния на ребрах равны 0, но этот аргумент справедлив, даже если это запрещено. См. Белк и Коннелли. ^[1] для подробного объяснения.

**Рисунок 2.** Для некоторых связей этот граф имеет одномерную реализацию (например, присвоение 1 каждому ребру). Однако, $C_{3}$ можно получить, сжимая ребро ${\bar {AB}}$ , поэтому граф не является 1-сглаживаемым.

2-сглаживаемые графы

Следующая теорема является фольклорной и показывает, что единственным запрещенным минором для 2-уплощенности является полный граф. $K_{4}$ .

Теорема. Граф является 2-сглаживаемым тогда и только тогда, когда он является частичным 2-деревом .

Доказательство. Доказательство можно найти в Belk & Connelly. ^[1] Для одного направления, поскольку уплощаемость замкнута относительно взятия подграфов, достаточно показать, что 2-деревья 2-сглаживаемы. 2-дерево с $n$ вершины можно построить рекурсивно , взяв 2-дерево с $n-1$ вершины и соединение новой вершины с вершинами существующего ребра. Базовый случай – это $K_{3}$ . Действуем индукцией по числу вершин. $n$ . Когда $n=3$ , рассмотрите любое задание на расстоянии $\delta$ по краям $K_{3}$ . Обратите внимание, что если $\delta$ не подчиняется неравенству треугольника , то эта ДСК не имеет реализации ни в одном измерении. Без ограничения общности разместим первую вершину $v_{1}$ в начале координат и во второй вершине $v_{2}$ вдоль оси x так, что $\delta _{12}$ удовлетворен. Третья вершина $v_{3}$ можно разместить на пересечении кругов с центрами $v_{1}$ и $v_{2}$ и радиусы $\delta _{13}$ и $\delta _{23}$ соответственно. Этот метод размещения называется построением линейки и циркуля . Следовательно, $K_{3}$ является 2-сплющиваемым.

Теперь предположим, что 2-дерево с $k$ вершины 2-сглаживаемы. По определению, 2-дерево с $k+1$ вершинами является 2-дерево с $k$ вершины, скажем $T$ и дополнительная вершина $u$ соединен с вершинами существующего ребра в $T$ . По индуктивному предположению, $T$ является 2-сплющиваемым. Наконец, используя тот же аргумент построения линейки и циркуля, что и в базовом случае, $u$ можно расположить так, чтобы оно лежало на плоскости. Таким образом, 2-деревья 2-сплющиваемы по индукции.

Если график $G$ не является частичным 2-деревом, то оно содержит $K_{4}$ как несовершеннолетний. Присвоение расстояния 1 краям $K_{4}$ минор и расстояние 0 до всех остальных ребер дает DCS с реализацией в 3-х измерениях как 1-скелет тетраэдров. Однако эта DCS не реализуется в двух измерениях: при попытке разместить четвертую вершину с помощью линейки и циркуля не все три круга, определяемые четвертой вершиной, пересекаются.

Пример. Рассмотрим граф на рисунке 2. Добавление ребра ${\bar {AC}}$ превращает его в 2-дерево; следовательно, это частичное 2-дерево. Таким образом, оно 2-сплющиваемо.

Пример. График колеса $W_{5}$ содержит $K_{4}$ как несовершеннолетний. Таким образом, оно не является 2-сглаживаемым.

3-сглаживаемые графы

Класс 3-сглаживаемых графов строго содержит класс частичных 3-деревьев. ^[1] Точнее, запрещенные миноры для частичных 3-деревьев представляют собой полный граф. $K_{5}$ , 1-скелет октаэдра $K_{2,2,2}$ , $V_{8}$ , и $C_{5}\times C_{2}$ , но $V_{8}$ , и $C_{5}\times C_{2}$ 3-сплющиваемы. ^[6] Эти графики показаны на рисунке 3. Кроме того, следующая теорема Белка и Коннелли ^[1] показывает, что единственными запрещенными минорами для 3-сглаживаемости являются $K_{5}$ и $K_{2,2,2}$ .

**Рисунок 3.** Интересующие графики 3-сглаживаемости.

Теорема. ^[1] Граф является 3-сглаживаемым тогда и только тогда, когда он не имеет $K_{5}$ или $K_{2,2,2}$ как несовершеннолетний.

Идея доказательства: доказательство, данное в книге Belk & Connelly. ^[1] предполагает, что $V_{8}$ , и $C_{5}\times C_{2}$ 3-реализуемы. Это доказано в той же статье с использованием математических инструментов теории жесткости, особенно тех, которые касаются тенсегрити. Полный график $K_{5}$ не является 3-сглаживаемым, и тот же аргумент, который показывает $K_{4}$ не является 2-сплющиваемым и $K_{3}$ здесь не работает 1-сглаживание: присвоение расстояния 1 краям $K_{5}$ дает DCS без реализации в трех измерениях. Рисунок 4 наглядно доказывает, что график $K_{2,2,2}$ не является 3-сглаживаемым. Вершины 1, 2 и 3 образуют вырожденный треугольник. Для ребер между вершинами 1–5 ребра $(1,4)$ и $(3,4)$ присвоено расстояние ${\sqrt {2}}$ всем остальным ребрам назначается расстояние 1. Вершины 1–5 имеют уникальное расположение в трех измерениях, с точностью до конгруэнтности. Вершина 6 имеет 2 возможных размещения в 3-х измерениях: по 1 на каждой стороне плоскости. $\Pi$ определяется вершинами 1, 2 и 4. Следовательно, ребро $(5,6)$ имеет два значения расстояния, которые могут быть реализованы в трех измерениях. Однако вершина 6 может вращаться вокруг плоскости $\Pi$ в 4-х измерениях, удовлетворяя всем ограничениям, поэтому ребро $(5,6)$ имеет бесконечно много значений расстояний, которые могут быть реализованы только в 4-х измерениях или выше. Таким образом, $K_{2,2,2}$ не является 3-сглаживаемым. Тот факт, что эти графы не являются 3-сглаженными, доказывает, что любой граф с любым $K_{5}$ или $K_{2,2,2}$ как минор не является 3-сглаживаемым.

Другое направление показывает, что если график $G$ не имеет $K_{5}$ или $K_{2,2,2}$ будучи несовершеннолетним, то $G$ может быть построено из частичных 3-деревьев, $V_{8}$ , и $C_{5}\times C_{2}$ через 1-суммы , 2-суммы и 3-суммы. Все эти графы 3-сглаживаемы, и эти операции сохраняют 3-сглаживаемость, поэтому $G$ является 3-сплющиваемым.

Методы этого доказательства приводят к следующему результату Белка и Коннелли. ^[1]

Теорема. ^[1] Каждый 3-реализуемый граф является подграфом графа, который может быть получен последовательностью 1-сумм, 2-сумм и 3-сумм графов. $K_{4}$ , $V_{8}$ , и $C_{5}\times C_{2}$ .

Пример. Предыдущую теорему можно применить, чтобы показать, что 1-остов куба 3-сплющиваем. Начните с графика $K_{4}$ , который является 1-скелетом тетраэдра. На каждой грани тетраэдра выполните 3-сумму с другой $K_{4}$ граф, т.е. склеить два тетраэдра по граням. Полученный граф содержит куб в качестве подграфа и является 3-сглаживаемым.

В высших измерениях

Давая запрещенную второстепенную характеристику $d$ -сглаживаемые графики, для измерения $d>3$ , является открытой проблемой. Для любого размера $d$ , $K_{d+2}$ и 1-скелет $d$ -мерный аналог октаэдра являются запрещенными минорами для $d$ -сплющиваемость. ^[1] Предполагается, что количество запрещенных несовершеннолетних для $d$ -уплощаемость асимптотически возрастает до числа запрещенных миноров для частичных $d$ -деревья, и их более $75$ запрещенные несовершеннолетние для частичных 4-деревьев. ^[1]

Альтернативная характеристика $d$ -сглаженные графы связывают сглаживаемость с конфигурационными пространствами Кэли. ^[2]^[7] См. раздел о подключении к пространствам конфигурации Кэли .

Связь с проблемой реализации графа

Учитывая систему ограничений расстояния и размерность $d$ , проблема реализации графа требует $d$ -мерная структура РСУ, если таковая существует. Есть алгоритмы реализации $d$ -сглаживаемые графики в $d$ -размеры, для $d\leq 3$ , которые выполняются за полиномиальное время в зависимости от размера графа. Для $d=1$ , реализовать каждое дерево в лесу в одномерном виде тривиально за полиномиальное время. Алгоритм для $d=2$ упоминается в Belk & Connelly. ^[1] Для $d=3$ , алгоритм в So & Ye ^[8] получает основу $r$ РСУ с использованием методов полуопределенного программирования , а затем использует метод «свертывания», описанный в Белке. ^[6] трансформировать $r$ в трехмерную структуру.

Уплощаемость по p -нормам

В этом разделе рассматриваются результаты уплощения графов в общих условиях. $p$ -нормы , для $1\leq p\leq \infty$ .

Связь с алгебраической геометрией

Определение уплощаемости графа при общем $p$ -норма может быть достигнута с использованием методов алгебраической геометрии , как это предложено Белком и Коннелли. ^[1] Вопрос о том, является ли график $G=(V,E)$ является $d$ - Flattenable эквивалентно определению двух полуалгебраических множеств равенства . Один алгоритм сравнения двух полуалгебраических множеств требует $(4|E|)^{O\left(nd|V|^{2}\right)}$ время. ^[9]

Подключение к пространствам конфигурации Кэли

Для общего $l_{p}$ -норм, существует тесная связь между уплощаемостью и пространствами конфигурации Кэли . ^[2]^[7] Следующая теорема и ее следствие найдены у Ситхарама и Уиллоуби. ^[2]

Теорема. ^[2] График $G$ является $d$ -сглаживаем тогда и только тогда, когда для каждого подграфа $H=G\setminus F$ из $G$ в результате удаления набора ребер $F$ от $G$ и любой $l_{p}^{p}$ -вектор расстояния $\delta _{H}$ такое, что DCS $(H,\delta _{H})$ имеет реализацию, $d$ -мерное конфигурационное пространство Кэли $(H,\delta _{H})$ над $F$ является выпуклым.

Следствие. График $G$ не $d$ -сглаживается, если существует некоторый подграф $H=G\setminus F$ из $G$ и некоторые $l_{p}^{p}$ -вектор расстояния $\delta$ такой, что $d$ -мерное конфигурационное пространство Кэли $(H,\delta _{H})$ над $F$ не является выпуклым.

l ₁ и l _∞2-Уплощение по нормам

The $l_{1}$ и $l_{\infty }$ нормы эквивалентны вращающимся осям в 2-х измерениях, ^[5] поэтому результаты о 2-сглаживании для любой нормы верны для обеих. В этом разделе используется $l_{1}$ -норм. Полный график $K_{4}$ 2-сплющиваема относительно $l_{1}$ -норма и $K_{5}$ 3-сплющиваема, но не 2-сплющена. ^[10] Эти факты способствуют следующим результатам о 2-уплощенности при $l_{1}$ -норма найдена в Ситхараме и Уиллоуби. ^[2]

Наблюдение. ^[2] Множество 2-сглаживаемых графов под $l_{1}$ -норма (и $l_{\infty }$ -norm) строго содержит множество 2-сглаживаемых графов при $l_{2}$ -норм.

Теорема. ^[2] 2-сумма 2-сглаживаемых графов является 2-сглаживаемой тогда и только тогда, когда не более одного графа имеет $K_{4}$ незначительный.

Тот факт, что $K_{4}$ является 2-сплющиваемым, но $K_{5}$ не имеет значения для запрещенной второстепенной характеризации для 2-сглаживаемых графов в соответствии с $l_{1}$ -норм. В частности, несовершеннолетние $K_{5}$ могут быть запрещены несовершеннолетние из-за 2-сглаживаемости. Следующие результаты исследуют эти возможности и дают полный набор запрещенных несовершеннолетних.

Теорема. ^[2] Банановый граф, или $K_{5}$ с удаленным одним ребром не является 2-сплющенным.

Наблюдение. ^[2] Граф, полученный удалением двух ребер, инцидентных одной вершине, из $K_{5}$ является 2-сплющиваемым.

Наблюдение. ^[2] Связные графы с 5 вершинами и 7 ребрами 2-сглаживаемы.

Единственный несовершеннолетний из $K_{5}$ слева — график колеса $W_{5}$ , и следующий результат показывает, что это один из запрещенных миноров.

Теорема. ^[11] Граф является 2-сглаживаемым относительно $l_{1}$ - или $l_{\infty }$ -norm тогда и только тогда, когда он не имеет ни одного из следующих графов в качестве минорных:

график колеса $W_{5}$ или
граф, полученный путем взятия 2-суммы двух копий $K_{4}$ и удаление общего края.

Связь с жесткостью конструкции

В этом разделе уплощаемость связана с концепциями структурной (комбинаторной) теории жесткости , такими как матроид жесткости . Следующие результаты касаются $l_{p}^{p}$ -дистанционный конус $\Phi _{n,l_{p}}$ , то есть совокупность всех $l_{p}^{p}$ -векторы расстояний, которые можно реализовать как конфигурацию $n$ точки в некотором измерении. Доказательство того, что это множество является конусом, можно найти у Болла. ^[12] $d$ -слой этого конуса $\Phi _{n,l_{p}}^{d}$ – это векторы, которые можно реализовать как конфигурацию $n$ указывает на $d$ -размеры. Проекция $\Phi _{n,l_{p}}$ или $\Phi _{n,l_{p}}^{d}$ на ребра графа $G$ это набор $l_{p}^{p}$ векторы расстояний, которые можно реализовать как длины ребер некоторого вложения $G$ .

Общее свойство графа $G$ является той, которую используют почти все структуры систем дистанционных ограничений, граф которых $G$ , иметь. Структура РСУ $(G,\delta )$ под $l_{p}$ -norm — это общая структура (по отношению к $d$ -сглаживаемость), если выполняются следующие два условия:

есть открытый район $\Omega$ из $\delta$ внутри конуса $\Phi _{n,l_{p}}$ , и
структура $d$ - Flattenable тогда и только тогда, когда все фреймворки в $\Omega$ являются $d$ -сплющенный.

Условие (1) обеспечивает, что окрестность $\Omega$ имеет полный ранг. Другими словами, $\Omega$ имеет размерность, равную размерности сглаживания полного графа $K_{n}$ под $l_{p}$ -норм. См. Китсон ^[13] для более подробного обсуждения общей структуры для $l_{p}$ -норм. Следующие результаты были найдены в Sitharam & Willoughby. ^[2]

Теорема. ^[2] График $G$ является $d$ -сглаживаемо тогда и только тогда, когда каждая общая структура $G$ является $d$ -сплющенный.

Теорема. ^[2] $d$ -сглаживаемость не является общим свойством графов, даже для $l_{2}$ -норм.

Теорема. ^[2] Общий $d$ -сглаживаемая структура графа $G$ существует тогда и только тогда, когда $G$ независим в общем $d$ матроид трехмерной жесткости.

Следствие. ^[2] График $G$ является $d$ -сглаживается только в том случае, если $G$ является независимым в $d$ матроид трехмерной жесткости.

Теорема. ^[2] Для общего $l_{p}$ -нормы, график $G$ является

независимый в общем $d$ -мерный матроид жесткости тогда и только тогда, когда проекция $d$ -слой $\Phi _{n,l_{p}}^{d}$ на края $G$ имеет размерность, равную числу ребер $G$ ;
максимально независимы в родовом $d$ Матроид трехмерной жесткости тогда и только тогда, когда проецируется $d$ -слой $\Phi _{n,l_{p}}^{d}$ на края $G$ сохраняет свою размерность, и эта размерность равна числу ребер $G$ ;
жесткий в $d$ -размеры тогда и только тогда, когда проецируем $d$ -слой $\Phi _{n,l_{p}}^{d}$ на края $G$ сохраняет свой размер;
не является независимым в общем $d$ -мерный матроид жесткости тогда и только тогда, когда размерность проекции $d$ -слой $\Phi _{n,l_{p}}^{d}$ на края $G$ строго меньше минимума размерности $\Phi _{n,l_{p}}^{d}$ и количество ребер $G$ .

Ссылки

^ Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к ^л ^м ^н ^тот ^п ^д Белк, Мария; Коннелли, Роберт (2007). «Реализуемость графов» . Дискретная и вычислительная геометрия . 37 (2): 125–137. дои : 10.1007/s00454-006-1284-5 . S2CID 12755057 .
^ Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к ^л ^м ^н ^тот ^п ^д Ситхарам, М.; Уиллоуби, Дж. (2014). «О уплощенности графов». Автоматизированный вывод по геометрии . Конспекты лекций по информатике. 9201 : 129–148. дои : 10.1007/978-3-319-21362-0_9 . ISBN 978-3-319-21361-3 . S2CID 23208 .
^ Лоран, Моник ; Варвициотис, Антониос (2012). «Грамманская размерность графа». Комбинаторная оптимизация . Конспекты лекций по информатике. Том. 7422. стр. 356–367. дои : 10.1007/978-3-642-32147-4_32 . ISBN 978-3-642-32146-7 . S2CID 18567150 .
^ Барвинок, А. (1995). «Проблемы дистанционной геометрии и выпуклые свойства квадратичных отображений» . Дискретная и вычислительная геометрия . 13 (2): 189–202. дои : 10.1007/BF02574037 . S2CID 20628306 .
^ Перейти обратно: ^а ^б Деза, Мишель ; Лоран, Моник (1997). Геометрия разрезов и метрика . Шпрингер-Верлаг Берлин Гейдельберг. дои : 10.1007/978-3-642-04295-9 . ISBN 978-3-540-61611-5 .
^ Перейти обратно: ^а ^б Белк, Мария (2007). «Реализуемость графов в трех измерениях» . Дискретная и вычислительная геометрия . 37 (2): 139–162. дои : 10.1007/s00454-006-1285-4 . S2CID 20238879 .
^ Перейти обратно: ^а ^б Ситхарам, Мира; Гао, Хэпин (2010). «Характеристика графов с выпуклыми и связными пространствами конфигурации Кэли» . Дискретная и вычислительная геометрия . 43 (3): 594–625. дои : 10.1007/s00454-009-9160-8 . S2CID 35819450 .
^ Итак, Энтони Ман-Чо; Йе, Иньюй (2006). «Подход полуопределенного программирования к теории тенсегрити и реализуемости графов». Материалы семнадцатого ежегодного симпозиума ACM-SIAM по дискретному алгоритму - SODA '06 . стр. 766–775. дои : 10.1145/1109557.1109641 . ISBN 0898716055 . S2CID 10134807 .
^ Басу, Саугата; Поллак, Ричард ; Мари-Франсуаза, Рой (2003). «Экзистенциальная теория реальности». Алгоритмы в реальной алгебраической геометрии . Алгоритмы и вычисления в математике. Том. 10. Шпрингер, Берлин, Гейдельберг. дои : 10.1007/3-540-33099-2_14 . ISBN 978-3-540-33098-1 .
^ Витсенхаузен, Ганс С. (1986). «Минимально размерное вложение конечных метрических пространств». Журнал комбинаторной теории . Серия А. 42 (2): 184–199. дои : 10.1016/0097-3165(86)90089-0 .
^ Фиорини, Самуэль; Хьюнь, Тони; Жоре, Гвенаэль; Варвициотис, Антониос (01 января 2017 г.). «Исключенные миноры для изометрической реализуемости на плоскости» . SIAM Journal по дискретной математике . 31 (1): 438–453. arXiv : 1511.08054 . дои : 10.1137/16M1064775 . hdl : 10356/81454 . ISSN 0895-4801 . S2CID 2579286 .
^ Болл, Кейт (1990). «Изометрическое вложение в lp-пространства» . Европейский журнал комбинаторики . 11 (4): 305–311. дои : 10.1016/S0195-6698(13)80131-X .
^ Китсон, Дерек (2015). «Конечная и бесконечно малая жесткость с многогранными нормами» . Дискретная и вычислительная геометрия . 54 (2): 390–411. arXiv : 1401.1336 . дои : 10.1007/s00454-015-9706-x . S2CID 15520982 .

[realizability-1] Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к ^л ^м ^н ^тот ^п ^д Белк, Мария; Коннелли, Роберт (2007). «Реализуемость графов» . Дискретная и вычислительная геометрия . 37 (2): 125–137. дои : 10.1007/s00454-006-1284-5 . S2CID 12755057 .

[flattenability-2] Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к ^л ^м ^н ^тот ^п ^д Ситхарам, М.; Уиллоуби, Дж. (2014). «О уплощенности графов». Автоматизированный вывод по геометрии . Конспекты лекций по информатике. 9201 : 129–148. дои : 10.1007/978-3-319-21362-0_9 . ISBN 978-3-319-21361-3 . S2CID 23208 .

[gramDimension-3] Лоран, Моник ; Варвициотис, Антониос (2012). «Грамманская размерность графа». Комбинаторная оптимизация . Конспекты лекций по информатике. Том. 7422. стр. 356–367. дои : 10.1007/978-3-642-32147-4_32 . ISBN 978-3-642-32146-7 . S2CID 18567150 .

[edgeBound-4] Барвинок, А. (1995). «Проблемы дистанционной геометрии и выпуклые свойства квадратичных отображений» . Дискретная и вычислительная геометрия . 13 (2): 189–202. дои : 10.1007/BF02574037 . S2CID 20628306 .

[flatDimBound-5] Перейти обратно: ^а ^б Деза, Мишель ; Лоран, Моник (1997). Геометрия разрезов и метрика . Шпрингер-Верлаг Берлин Гейдельберг. дои : 10.1007/978-3-642-04295-9 . ISBN 978-3-540-61611-5 .

[realizability2-6] Перейти обратно: ^а ^б Белк, Мария (2007). «Реализуемость графов в трех измерениях» . Дискретная и вычислительная геометрия . 37 (2): 139–162. дои : 10.1007/s00454-006-1285-4 . S2CID 20238879 .

[cayleyConfig-7] Перейти обратно: ^а ^б Ситхарам, Мира; Гао, Хэпин (2010). «Характеристика графов с выпуклыми и связными пространствами конфигурации Кэли» . Дискретная и вычислительная геометрия . 43 (3): 594–625. дои : 10.1007/s00454-009-9160-8 . S2CID 35819450 .

[3_realizability_algo-8] Итак, Энтони Ман-Чо; Йе, Иньюй (2006). «Подход полуопределенного программирования к теории тенсегрити и реализуемости графов». Материалы семнадцатого ежегодного симпозиума ACM-SIAM по дискретному алгоритму - SODA '06 . стр. 766–775. дои : 10.1145/1109557.1109641 . ISBN 0898716055 . S2CID 10134807 .

[basu2003algebraic-9] Басу, Саугата; Поллак, Ричард ; Мари-Франсуаза, Рой (2003). «Экзистенциальная теория реальности». Алгоритмы в реальной алгебраической геометрии . Алгоритмы и вычисления в математике. Том. 10. Шпрингер, Берлин, Гейдельберг. дои : 10.1007/3-540-33099-2_14 . ISBN 978-3-540-33098-1 .

[witsenhausen1986minimum-10] Витсенхаузен, Ганс С. (1986). «Минимально размерное вложение конечных метрических пространств». Журнал комбинаторной теории . Серия А. 42 (2): 184–199. дои : 10.1016/0097-3165(86)90089-0 .

[11] Фиорини, Самуэль; Хьюнь, Тони; Жоре, Гвенаэль; Варвициотис, Антониос (01 января 2017 г.). «Исключенные миноры для изометрической реализуемости на плоскости» . SIAM Journal по дискретной математике . 31 (1): 438–453. arXiv : 1511.08054 . дои : 10.1137/16M1064775 . hdl : 10356/81454 . ISSN 0895-4801 . S2CID 2579286 .

[l1_lower_1-12] Болл, Кейт (1990). «Изометрическое вложение в lp-пространства» . Европейский журнал комбинаторики . 11 (4): 305–311. дои : 10.1016/S0195-6698(13)80131-X .

[general_position-13] Китсон, Дерек (2015). «Конечная и бесконечно малая жесткость с многогранными нормами» . Дискретная и вычислительная геометрия . 54 (2): 390–411. arXiv : 1401.1336 . дои : 10.1007/s00454-015-9706-x . S2CID 15520982 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]