График единичного расстояния

Геометрический граф с единичными длинами ребер

Граф единичных расстояний с 16 вершинами и 40 ребрами.

В математике , особенно в геометрической теории графов , граф единичных расстояний — это граф , сформированный из набора точек евклидовой плоскости путем соединения двух точек всякий раз, когда расстояние между ними равно единице. Чтобы отличить эти графы от более широкого определения, которое позволяет некоторым несмежным парам вершин находиться на расстоянии один, их также можно назвать графами строгих единичных расстояний или точными графами единичных расстояний . Как наследственное семейство графов , они могут быть охарактеризованы запрещенными индуцированными подграфами . К графам единичных расстояний относятся графы кактусов , графы спичек и пенни-графы , а также графы гиперкубов . Обобщенные графы Петерсена представляют собой нестрогие графы единичных расстояний.

Нерешенная проблема Пола Эрдеша спрашивает, сколько ребер может иметь граф единичных расстояний на вершинах. Самая известная нижняя граница немного выше линейной по - далеко от верхней границы и пропорциональна . Количество цветов, необходимых для раскраски графов единичных расстояний, также неизвестно ( проблема Хадвигера-Нельсона ): для некоторых графов единичных расстояний требуется пять цветов, и каждый граф единичных расстояний можно раскрасить семью цветами. Для каждого алгебраического числа существует граф единичных расстояний с двумя вершинами, которые должны находиться на этом расстоянии друг от друга. Согласно теореме Бекмана-Куорлза , единственные плоские преобразования, сохраняющие все графы единичных расстояний, — это изометрии . ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n^{4/3}}$

Можно эффективно построить граф единичных расстояний по его точкам. Нахождение всех единичных расстояний имеет применение в сопоставлении с образцом , где оно может стать первым шагом в поиске конгруэнтных копий более крупных образцов. Однако определение того, может ли данный граф быть представлен в виде графа единичных расстояний, является NP-трудным и, более конкретно, полным для экзистенциальной теории действительных чисел .

Определение

Граф единичных расстояний для набора точек на плоскости — это неориентированный граф, вершинами которого являются эти точки , с ребром между двумя вершинами, когда их евклидово расстояние равно единице. Абстрактный граф называется графом с единичными расстояниями, если можно найти различные местоположения на плоскости для его вершин, так что его ребра имеют единичную длину и все несмежные пары вершин имеют неединичные расстояния. Когда это возможно, абстрактный граф изоморфен графу единичных расстояний выбранных местоположений. Альтернативно, в некоторых источниках используется более широкое определение, позволяющее несмежным парам вершин находиться на единичном расстоянии. Полученные графы являются подграфами графов единичных расстояний (как определено здесь). ^[2] Там, где терминология может быть неоднозначной, графы, в которых неребра должны находиться на расстоянии неединичного расстояния друг от друга, могут называться строгими графами единичных расстояний ^[3] или точными графами единичных расстояний . ^[2] Подграфы графов единичных расстояний — это эквивалентные графы, которые можно нарисовать на плоскости, используя только одну длину ребра. ^[4] Для краткости в этой статье они называются «нестрогими графами единичных расстояний».

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

Примеры

Полный граф на двух вершинах является графом единичных расстояний, как и полный граф на трех вершинах ( граф треугольника ), но не полный граф на четырех вершинах. ^[3] Обобщая треугольный граф, каждый граф циклов представляет собой граф единичных расстояний, реализованный в виде правильного многоугольника . ^[4] Два графа конечных единичных расстояний, соединенные в одной общей вершине, образуют еще один граф единичных расстояний, поскольку один можно вращать относительно другого, чтобы избежать нежелательных дополнительных единичных расстояний. ^[6] Таким образом соединяя графы, каждое конечное дерево или граф кактуса можно реализовать как граф единичных расстояний. ^[7]

Любое декартово произведение графов единичных расстояний дает другой граф единичных расстояний; однако то же самое нельзя сказать о некоторых других распространенных графовых продуктах. Например, сильное произведение графов , примененное к любым двум непустым графам, дает полные подграфы с четырьмя вершинами, которые не являются графами единичных расстояний. Декартовы произведения графов путей образуют сетчатые графы любой размерности, декартовы произведения полного графа на двух вершинах являются графами гиперкубов , ^[8] и декартовы произведения треугольных графов являются графами Хэмминга . ^[9] ${\displaystyle H(d,3)}$

Другие конкретные графы, которые являются графами единичных расстояний, включают граф Петерсена , ^[10] граф Хивуда , [ ^11] граф колеса (единственный граф колеса, который является графом единичного расстояния), ^[3] и веретено Мозера и граф Голомба ( небольшие 4- хроматические графы расстояний). ^[12] Все обобщенные графы Петерсена , такие как изображенный граф Мёбиуса – Кантора , являются нестрогими графами единичных расстояний. ^[13] ${\displaystyle W_{7}}$

Спичечные графы — это частный случай графов единичных расстояний, в которых ребра не пересекаются. Каждый граф из спичек является плоским графом , ^[14] но некоторые в остальном плоские графы единичных расстояний (например, веретено Мозера) имеют пересечение в каждом представлении в виде графа единичных расстояний. Кроме того, в контексте графиков единичных расстояний термин «планарный» следует использовать с осторожностью, поскольку некоторые авторы используют его для обозначения плоскости, в которой определяются единичные расстояния, а не для запрета на пересечения. ^[3] Пенни -графы представляют собой еще более частный случай графов с единичными расстояниями и спичечных графов, в которых каждая несмежная пара вершин находится на расстоянии более одной единицы друг от друга. ^[14]

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

Количество ребер

Нерешенная задача по математике :

Сколько единичных расстояний можно определить по набору точек? ${\displaystyle n}$

(еще нерешенные задачи по математике)

Пол Эрдеш  (1946) поставил задачу оценить, сколько пар точек в наборе точек может находиться на единичном расстоянии друг от друга. С точки зрения теории графов, вопрос заключается в том, насколько плотным может быть граф единичных расстояний, и публикация Эрдёша по этому вопросу была одной из первых работ в экстремальной теории графов . ^[15] Графы гиперкуба и графы Хэмминга обеспечивают нижнюю границу количества единичных расстояний, пропорциональную Рассмотрев точки в квадратной сетке с тщательно выбранным интервалом, Эрдеш нашел улучшенную нижнюю границу формы ${\displaystyle n}$ ${\displaystyle n\log n.}$

$${\displaystyle n^{1+c/\log \log n}}$$

^[16] ${\displaystyle c}$

$${\displaystyle {\sqrt[{3}]{\frac {29n^{4}}{4}}}\approx 1.936n^{4/3}.}$$

неравенством числа пересеченийтеоремой Семереди-Троттера^[17]

Для небольших значений (до 14 по состоянию на 2022 год ) известно точное максимальное количество возможных ребер. Для этих чисел ребер: ^[18] ${\displaystyle n}$^{[обновлять]} ${\displaystyle n=2,3,4,\dots }$

1, 3, 5, 7, 9, 12, 14, 18, 20, 23, 27, 30, 33, ... (последовательность A186705 в OEIS )

Запрещенные подграфы

Если данный граф не является нестрогим графом единичных расстояний, то он не является и суперграфом . Похожая идея работает для графов со строгими единичными расстояниями, но с использованием концепции индуцированного подграфа — подграфа, сформированного из всех ребер между парами вершин в заданном подмножестве вершин. Если это не строгий граф единичных расстояний, то не существует и другого графа , имеющего индуцированный подграф. Из-за этих отношений между тем, является ли подграф или его суперграф графом единичных расстояний, можно описывать графы единичных расстояний с помощью их запрещенных подграфов . Это минимальные графы, не являющиеся графами единичных расстояний данного типа. Их можно использовать, чтобы определить, является ли данный граф графом единичных расстояний любого типа. является нестрогим графом единичных расстояний тогда и только тогда, когда он не является суперграфом запрещенного графа для нестрогих графов единичных расстояний. является строгим графом единичных расстояний тогда и только тогда, когда он не является индуцированным суперграфом запрещенного графа для строгих графов единичных расстояний. ^[8] ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$

Как для нестрогих, так и для строгих графов единичных расстояний запрещенные графы включают как полный граф, так и полный двудольный граф . Для , где бы ни располагались вершины на двухвершинной стороне этого графа, существует не более двух позиций на единичном расстоянии от них для размещения трех других вершин, поэтому невозможно разместить все три вершины в разных точках. ^[8] Это единственные два запрещенных графа для нестрогих графов единичных расстояний, содержащих до пяти вершин; существует шесть запрещенных графов с числом вершин до семи ^[6] и 74 графов с числом вершин до девяти. Поскольку склеивание двух графов единичных расстояний (или их подграфов) в вершине создает строгие (соответственно нестрогие) графы единичных расстояний, каждый запрещенный граф является двусвязным графом , который не может быть сформирован в результате этого процесса склеивания. ^[19] ${\displaystyle K_{4}}$ ${\displaystyle K_{2,3}}$ ${\displaystyle K_{2,3}}$

Граф -колесо можно реализовать как строгий граф единичных расстояний, шесть вершин которого образуют единичный правильный шестиугольник , а седьмая - в центре шестиугольника. Удаление одного из ребер из центральной вершины создает подграф, который по-прежнему имеет ребра единичной длины, но не является строгим графом единичных расстояний. Размещение его вершин в правильном шестиугольнике — единственный способ ( с точностью до конгруэнтности ) разместить вершины в разных местах, так что соседние вершины находятся на единичном расстоянии друг от друга, и это размещение также помещает две конечные точки недостающего ребра на единичное расстояние. . Таким образом, это запрещенный граф для строгих графов единичных расстояний ^[20] , но не один из шести запрещенных графов для нестрогих графов единичных расстояний. Другие примеры графов, которые являются нестрогими графами единичных расстояний, но не строгими графами единичных расстояний, включают граф, образованный удалением внешнего ребра из , и граф с шестью вершинами, сформированный из треугольной призмы путем удаления ребра из одного из ее треугольников. ^[19] ${\displaystyle W_{7}}$ ${\displaystyle W_{7}}$

Алгебраические числа и жесткость

Для каждого алгебраического числа можно построить граф единичных расстояний, в котором некоторая пара вершин находится на расстоянии во всех представлениях единичного расстояния . ^[21] Из этого результата следует конечная версия теоремы Бекмана–Куорлза : для любых двух точек , находящихся на расстоянии друг от друга, существует конечный жесткий граф единичных расстояний, содержащий и такой, что любое преобразование плоскости, сохраняющее единичные расстояния в этот граф также сохраняет расстояние между и . ^[22] Полная теорема Бекмана-Куорлза утверждает, что единственные преобразования евклидовой плоскости (или евклидова пространства более высокой размерности), которые сохраняют единичные расстояния, - это изометрии . Аналогично, для бесконечного графа единичных расстояний, порожденного всеми точками плоскости, все автоморфизмы графа сохраняют все расстояния на плоскости, а не только единичные расстояния. ^[23] ${\displaystyle \alpha }$ ${\displaystyle G}$ ${\displaystyle \alpha }$ ${\displaystyle G}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle \alpha }$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle p}$ ${\displaystyle q}$

Если - алгебраическое число модуля 1, не являющееся корнем из единицы , то целочисленные комбинации степеней образуют конечно порожденную подгруппу аддитивной группы комплексных чисел , график единичных расстояний которых имеет бесконечную степень . Например, может быть выбран в качестве одного из двух комплексных корней полинома , создавая граф единичных расстояний бесконечной степени с четырьмя генераторами. ^[24] ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle z^{4}-z^{3}-z^{2}-z+1}$

Раскраска

Нерешенная задача по математике :

Каково максимально возможное хроматическое число графа единичных расстояний?

(еще нерешенные задачи по математике)

Проблема Хадвигера -Нельсона касается хроматического числа графов единичных расстояний, а точнее, бесконечного графа единичных расстояний, образованного из всех точек евклидовой плоскости. По теореме де Брейна-Эрдёша , которая предполагает аксиому выбора , это эквивалентно запросу наибольшего хроматического числа графа конечных единичных расстояний. Существуют графы единичных расстояний, требующие пяти цветов в любой правильной раскраске ^[25] , и все графы единичных расстояний могут быть раскрашены не более чем в семь цветов. ^[26]

Семираскраска бесконечного графа единичных расстояний, сформированного из всех точек плоскости, и четыреххроматическое веретено Мозера, встроенное в граф единичных расстояний.

Отвечая на другой вопрос Пола Эрдеша, можно сказать, что для графиков единичных расстояний без треугольников может потребоваться четыре цвета. ^[27]

Перечисление

Число строгих графов единичных расстояний на помеченных вершинах не превышает ^[2] ${\displaystyle n\geq 4}$

$${\displaystyle {\binom {n(n-1)}{2n}}=O\left(2^{{\bigl (}4+o(1){\bigr )}n\log _{2}n}\right),}$$

обозначения «большое О»

Обобщение на более высокие измерения

Определение графа единичных расстояний естественным образом можно обобщить на любое многомерное евклидово пространство . В трех измерениях графы единичных расстояний точек имеют не более ребер, где – очень медленно растущая функция, связанная с обратной функцией Аккермана . ^[28] Этот результат приводит к аналогичной оценке количества ребер трехмерных графов относительной окрестности . ^[29] В четырех или более измерениях любой полный двудольный граф представляет собой граф единичных расстояний, реализованный путем размещения точек на двух перпендикулярных окружностях с общим центром, поэтому графы единичных расстояний могут быть плотными графами . ^[7] Формулы перечисления для графов единичных расстояний обобщаются на более высокие измерения и показывают, что в измерениях четыре или более количество строгих графов единичных расстояний намного больше, чем количество подграфов графов единичных расстояний. ^[2] ${\displaystyle n}$ ${\displaystyle n^{3/2}\beta (n)}$ ${\displaystyle \beta }$

Любой конечный граф может быть встроен как граф единичных расстояний в достаточно высокой размерности. Некоторым графам могут потребоваться совершенно разные измерения для встраивания в виде нестрогих графов единичных расстояний и строгих графов единичных расстояний. Например, граф короны -вершины может быть встроен в четыре измерения как нестрогий граф единичных расстояний (то есть так, чтобы все его ребра имели единичную длину). Однако для этого требуется, чтобы как минимум измерения были встроены в строгий граф единичных расстояний, чтобы его ребра были единственными парами единичных расстояний. ^[30] Размерность, необходимая для реализации любого данного графа как строгого единичного графа, не превышает двойной его максимальной степени. ^[31] ${\displaystyle 2n}$ ${\displaystyle n-2}$

Вычислительная сложность

Построение графа единичных расстояний из его точек является важным шагом для других алгоритмов поиска конгруэнтных копий некоторого шаблона в большем наборе точек. Эти алгоритмы используют эту конструкцию для поиска позиций-кандидатов, где присутствует одно из расстояний в шаблоне, а затем используют другие методы для проверки остальной части шаблона для каждого кандидата. ^[32] К этой проблеме можно применить метод Матоушека (1993), ^[32] позволяющий найти алгоритм для нахождения графика единичных расстояний плоского множества точек во времени, где – медленно растущая функция повторного логарифма . ^[33] ${\displaystyle n^{4/3}2^{O(\log ^{*}n)}}$ ${\displaystyle \log ^{*}}$

NP -трудно (а точнее, полно для экзистенциальной теории реальных чисел ) проверить, является ли данный граф графом единичных расстояний на плоскости (строгим или нестрогим). ^[34] Также NP-полным является определение того, имеет ли планарный граф единичных расстояний гамильтонов цикл , даже если все вершины графа имеют известные целочисленные координаты. ^[35]

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

Примечания

1. Гриффитс (2019).
2. Алон и Купавский (2014).
3. Джервасио, Лим и Маэхара (2008).
4. Карми и др. (2008).
5. Хьюсон и Сен (1995).
6. Чилакамарри и Махони (1995).
7. Эрдеш, Харари и Тутте (1965).
8. Хорват и Пизански (2010).
9. Брауэр и Хамерс (2012).
10. Эрдеш, Харари и Тутте (1965); Гриффитс (2019)
11. Гербрахт (2009).
12. Сойфер (2008), стр. 14–15, 19.
13. Житник, Хорват и Писански (2012).
14. Лаволле и Сванепол (2022).
15. Семереди (2016).
16. Эрдеш (1990).
17. Спенсер, Семереди и Троттер (1984); Кларксон и др. (1990); Пач и Тардос (2005); Агостон и Палвёлдьи (2022)
18. Агостон и Палвёлдьи (2022).
19. Globus & Parshall (2020).
20. Сойфер (2008), с. 94.
21. Маэхара (1991, 1992).
22. Тышка (2000).
23. Бекман и Куорлз (1953).
24. Радченко (2021).
25. Лангин (2018); де Грей (2018)
26. Сойфер (2008), с. 17.
27. Вормальд (1979); Чилакамарри (1995 год); О'Доннелл (1995).
28. Кларксон и др. (1990).
29. Яромчик и Туссен (1992).
30. Эрдеш и Симоновиц (1980).
31. Маэхара и Рёдль (1990).
32. Брасс (2002).
33. Матушек (1993); см. также Chan & Zheng (2022), где описан тесно связанный алгоритм для составления списка инцидентов между точками и линиями во времени . ${\displaystyle O(n^{4/3})}$
34. Шефер (2013).
35. Итай, Пападимитриу и Шварцфитер (1982).

Источники

• Агостон, Питер; Палвёлдьи, Дёмётёр (апрель 2022 г.), «Улучшенный постоянный коэффициент для задачи единичного расстояния», Studia Scientiarum Mathematicarum Hungarica , Akademiai Kiado Zrt., 59 (1): 40–57, arXiv : 2006.06285 , doi : 10.1556/012.2022.01517 , S2CID  218479287
• Алон, Нога ; Купавский, Андрей (2014), «Два понятия графов единичных расстояний» (PDF) , Журнал комбинаторной теории , Серия A, 125 : 1–17, doi : 10.1016/j.jcta.2014.02.006, MR  3207464, S2CID  12043969
• Бекман, Ф.С.; Куорлз, Д.А. младший (1953), «Об изометриях евклидовых пространств», Труды Американского математического общества , 4 (5): 810–815, doi : 10.2307/2032415 , JSTOR  2032415, MR  0058193
• Брасс, Питер (2002), «Задачи комбинаторной геометрии в распознавании образов», Discrete & Computational Geometry , 28 (4): 495–510, doi : 10.1007/s00454-002-2884-3 , MR  1949897
• Брауэр, Андрис Э .; Хемерс, Виллем Х. (2012), Спектры графов , Universitext, Нью-Йорк: Springer, стр. 178, номер домена : 10.1007/978-1-4614-1939-6, ISBN 978-1-4614-1938-9, МР  2882891
• Карми, Пас; Дуймович, Вида ; Морен, Пэт ; Вуд, Дэвид Р. (2008), «Различные расстояния в графических рисунках», Electronic Journal of Combinatorics , 15 (1): Research Paper 107, arXiv : 0804.3690 , doi : 10.37236/831, MR  2438579, S2CID  2955082
• Чан, Тимоти М .; Чжэн, Да Вэй (2022), «Задача Хопкрофта, бритье по лог-звезде, 2-мерный дробный каскад и деревья решений», в Наоре, Джозеф (Сеффи); Бухбиндер, Нив (ред.), Труды симпозиума ACM-SIAM 2022 по дискретным алгоритмам, SODA 2022, Виртуальная конференция / Александрия, Вирджиния, США, 9–12 января 2022 г. , Общество промышленной и прикладной математики, стр. 190– 210, arXiv : 2111.03744 , doi : 10.1137/1.9781611977073.10, S2CID  243847672
• Чилакамарри, Киран Б. (1995), «4-хроматический граф единичных расстояний без треугольников», Geombinatorics , 4 (3): 64–76, MR  1313386
• Чилакамарри, Киран Б.; Махони, Кэролайн Р. (1995), «Максимальные и минимальные запрещенные графы единичных расстояний на плоскости», Бюллетень Института комбинаторики и ее приложений , 13 : 35–43, MR  1314500по цитате Globus & Parshall (2020).
• Кларксон, Кеннет Л .; Эдельсбруннер, Герберт ; Гибас, Леонидас Дж .; Шарир, Миша ; Вельцль, Эмо (1990), «Оценки комбинаторной сложности расположения кривых и сфер», Дискретная и вычислительная геометрия , 5 (2): 99–160, doi : 10.1007/BF02187783 , MR  1032370, S2CID  28143698
• де Грей, Обри DNJ (2018), «Хроматическое число плоскости не менее 5», Geombinatorics , 28 : 5–18, arXiv : 1804.02385 , MR  3820926
• Эрдеш, Пол (1946), «О множествах расстояний между точками», American Mathematical Monthly , 53 (5): 248–250, doi : 10.2307/2305092, JSTOR  2305092 ${\displaystyle n}$
• Эрдеш, Пол ; Харари, Фрэнк ; Тутте, Уильям Т. (1965), «О размерности графа» (PDF) , Mathematika , 12 (2): 118–122, doi : 10.1112/S0025579300005222, hdl : 2027.42/152495 , MR  0188096
• Эрдеш, Пол ; Симоновиц, Миклош (1980), «О хроматическом числе геометрических графов», Ars Combinatoria , 9 : 229–246., по словам Сойфера (2008, стр. 97).
• Эрдеш, Пол (1990), «Некоторые из моих любимых нерешенных задач», Бейкер, А.; Боллобас, Б.; Хайнал, А. (ред.), Дань уважения Полу Эрдешу , Cambridge University Press, стр. 467–478, ISBN 0-521-38101-0, МР  1117038; см., в частности, стр. 475
• Гербрахт, Эберхард Х.-А. (2009), Вложения графа Хивуда на одиннадцать единиц расстояния , arXiv : 0912.5395 , Bibcode : 2009arXiv0912.5395G
• Джервасио, Северино В.; Лим, Иветт Ф.; Маэхара, Хироши (2008), «Плоские графы единичных расстояний, имеющие плоское дополнение единичных расстояний», Discrete Mathematics , 308 (10): 1973–1984, doi : 10.1016/j.disc.2007.04.050
• Глобус, Эйдан; Паршалл, Ганс (2020), «Малые графы единичных расстояний на плоскости», Бюллетень Института комбинаторики и ее приложений , 90 : 107–138, arXiv : 1905.07829 , MR  4156400
• Гриффитс, Мартин (июнь 2019 г.), «103.27 Свойство определенного графа единичных расстояний», The Mathematical Gazette , 103 (557): 353–356, doi : 10.1017/mag.2019.74, S2CID  233361952
• Хорват, Борис; Писанский, Томаж (2010), «Продукты графов единичных расстояний», Дискретная математика , 310 (12): 1783–1792, doi : 10.1016/j.disc.2009.11.035 , MR  2610282
• Хьюсон, Марк Л.; Сен, Арунабха (1995), «Алгоритмы планирования вещания для радиосетей», Конференция по военной связи, IEEE MILCOM '95 , том. 2, стр. 647–651, номер документа : 10.1109/MILCOM.1995.483546, ISBN. 0-7803-2489-7, S2CID  62039740
• Итай, Алон; Пападимитриу, Христос Х .; Шварцфитер, Хайме Луис (1982), «Пути Гамильтона в сеточных графах», SIAM Journal on Computing , 11 (4): 676–686, CiteSeerX  10.1.1.383.1078 , doi : 10.1137/0211056, MR  0677661
• Яромчик, Ежи В.; Туссен, Годфрид Т. (1992), «Графы относительной окрестности и их родственники», Proceedings of the IEEE , 80 (9): 1502–1517, doi : 10.1109/5.163414
• Лангин, Кэти (18 апреля 2018 г.), «Математик-любитель решает математическую задачу, возникшую десятилетия назад», Science
• Лаволле, Жереми; Свейнпол, Конрад Дж. (2022), «Ограничение количества ребер спичечных графов», SIAM Journal on Discrete Mathematics , 36 (1): 777–785, arXiv : 2108.07522 , doi : 10.1137/21M1441134, MR  4399020, S2CID  23714262 4
• Маэхара, Хироши (1991), «Расстояния в жестком графе единичных расстояний на плоскости», Discrete Applied Mathematics , 31 (2): 193–200, doi : 10.1016/0166-218X(91)90070-D
• Маэхара, Хироши (1992), «Расширение гибкой структуры единичных стержней до жесткой», Discrete Mathematics , 108 (1–3): 167–174, doi : 10.1016/0012-365X(92)90671-2 , MR  1189840
• Маэхара, Хироши; Рёдль, Войтех (1990), «О размерности представления графа с помощью графа единичных расстояний», Graphs and Combinatorics , 6 (4): 365–367, doi : 10.1007/BF01787703, S2CID  31148911
• Матушек, Иржи (1993), «Поиск диапазона с помощью эффективных иерархических разрезов», Дискретная и вычислительная геометрия , 10 (2): 157–182, doi : 10.1007/BF02573972 , MR  1220545
• О'Доннелл, Пол (1995), «40-вершинный 4-хроматический граф расстояний без треугольников», Geombinatorics , 5 (1): 31–34, MR  1337155
• Пах, Янош ; Тардос, Габор (2005), «Запрещенные шаблоны и единичные расстояния», Митчелл, Джозеф С.Б.; Роте, Гюнтер (ред.), Труды 21-го симпозиума ACM по вычислительной геометрии, Пиза, Италия, 6–8 июня 2005 г. , Ассоциация вычислительной техники, стр. 1–9, doi : 10.1145/1064092.1064096, MR  2460341, S2CID  18752227
• Радченко, Даниил (2021), «Графы единичных расстояний и алгебраические целые числа», Дискретная и вычислительная геометрия , 66 (1): 269–272, doi : 10.1007/s00454-019-00152-4, hdl : 21.11116/0000-0006- 9CFD-E , MR  4270642, S2CID  119682489
• Шефер, Маркус (2013), «Реализуемость графов и связей», в Пач, Янош (редактор), « Тридцать эссе по геометрической теории графов» , Springer, стр. 461–482, CiteSeerX  10.1.1.220.9651 , doi :10.1007/ 978-1-4614-0110-0_24, ISBN 978-1-4614-0109-4
• Сойфер, Александр (2008), Математическая книжка-раскраска , Springer-Verlag, ISBN 978-0-387-74640-1
• Спенсер, Джоэл ; Семереди, Эндре ; Троттер, Уильям Т. (1984), «Единичные расстояния в евклидовой плоскости», в Боллобасе, Бела (редактор), Теория графов и комбинаторика , Лондон: Academic Press, стр. 293–308, ISBN 978-0-12-111760-3, МР  0777185
• Семереди, Эндре (2016), «Проблема единичного расстояния Эрдёша», в Нэше, Джон Форбс-младший ; Рассиас, Майкл Т. (ред.), Открытые задачи по математике , Чам, Швейцария: Springer, стр. 459–477, doi : 10.1007/978-3-319-32162-2_15, MR  3526946{{citation}}: CS1 maint: несколько имен: список редакторов ( ссылка )
• Тышка, Аполониуш (2000), «Дискретные версии теоремы Бекмана-Куорлза», Aequationes Mathematicae , 59 (1–2): 124–133, arXiv : math/9904047 , doi : 10.1007/PL00000119, MR  1741475, S2CID  1480318 2
• Вормальд, Николас (1979), «4-хроматический граф со специальным рисунком плоскости», Журнал Австралийского математического общества , серия A, 28 (1): 1–8, doi : 10.1017/S1446788700014865 , MR  0541161, S2CID  124067465
• Житник, Арьяна; Хорват, Борис; Писански, Томаж (2012), «Все обобщенные графы Петерсена являются графами единичных расстояний», Журнал Корейского математического общества , 49 (3): 475–491, doi : 10.4134/JKMS.2012.49.3.475 , MR  2953031

Внешние ссылки

• Венкатасубраманиан, Суреш, «Задача 39: расстояния между множествами точек в R2 и R3», Проект открытых проблем
• Вайсштейн, Эрик В. , «График единичных расстояний», MathWorld