Диаграмма Вороного конечного множества точек S на плоскости представляет такое разбиение плоскости, при котором каждая область этого разбиения образует множество точек, более близких к одному из элементов множества S, чем к любому другому элементу множества.
Вычислительная геометрия — раздел информатики, в котором рассматриваются алгоритмы для решения геометрических задач.
Раскраска графа — теоретико-графовая конструкция, частный случай разметки графа. При раскраске элементам графа ставятся в соответствие метки с учётом определённых ограничений; эти метки традиционно называются «цветами». В простейшем случае такой способ окраски вершин графа, при котором любым двум смежным вершинам соответствуют разные цвета, называется раскраской вершин. Аналогично раскраска рёбер присваивает цвет каждому ребру так, чтобы любые два смежных ребра имели разные цвета. Наконец, раскраска областей планарного графа назначает цвет каждой области, так, что каждые две области, имеющие общую границу, не могут иметь одинаковый цвет.
Триангуля́ция Делоне́ — триангуляция для заданного множества точек S на плоскости, при которой для любого треугольника все точки из S за исключением точек, являющихся его вершинами, лежат вне окружности, описанной вокруг треугольника. Обозначается DT(S). Впервые описана в 1934 году советским математиком Борисом Делоне.
В теории графов графом без треугольников называется неориентированный граф, в котором никакие три вершины не образуют треугольник из рёбер. Графы без треугольников можно определить также как графы с кликовым числом ≤ 2, графы с обхватом ≥ 4, графы без порождённых 3-циклов, или как локально независимые графы.
В теории графов максимальным независимым множеством, максимальным устойчивым множеством, или максимальным стабильным множеством называется независимое множество, не являющееся подмножеством другого независимого множества. То есть это такое множество вершин S, что любое ребро графа имеет хотя бы одну конечную вершину, не принадлежащую S, и любая вершина не из S имеет хотя бы одну соседнюю в S. Максимальное независимое множество является также доминирующим в графе, а любое доминирующее множество, являющееся независимым, должно быть максимальным независимым, поэтому максимальные независимые множества также называют независимыми доминирующими множествами. Граф может иметь много максимальных независимых множеств в широком диапазоне размеров.
Задача о триангуляции многоугольника — классическая задача комбинаторной и вычислительной геометрии, состоящая в нахождении триангуляции многоугольника без дополнительных вершин.
Граф ближайших соседей (ГБС) для множества P, состоящего из n объектов в метрическом пространстве — это ориентированный граф, вершинами которого служат элементы множества P, в котором существует ориентированное ребро из p в q, если q является ближайшим соседом p.
Теорема о планарном разбиении — это форма изопериметрического неравенства для планарных графов, которое утверждает, что любой планарный граф может быть разбит на более мелкие части путём удаления небольшого числа вершин. В частности, удалением O(√n) вершин из графа с n вершинами можно разбить граф на несвязные подграфы, каждый из которых имеет не более 2n/3 вершин.
Индифферентный граф — это неориентированный граф, построенный путём назначения вещественного числа каждой вершине и соединения двух вершин ребром, когда их числа отличаются не более чем на единицу. Индифферентные графы являются также графами пересечений множеств единичных отрезков или интервалов с определённым свойством вложения. Основываясь на этих двух типах интервальных представлений, эти графы называются также графами единичных отрезков или собственными интервальными графами. Индифферентные графы образуют подкласс интервальных графов.
Евклидово минимальное остовное дерево — это минимальное остовное дерево набора из n точек на плоскости, где вес ребра между любой парой точек является евклидовым расстоянием между двумя точками. Простыми терминами, EMST связывает набор точек с помощью отрезков так, что общая длина всех отрезков минимальна и любая точка может быть достигнута из другой точки по этим отрезкам.
Задача о паре ближайших точек — это задача вычислительной геометрии. Дано n точек в метрическом пространстве, нужно найти пару точек с наименьшим расстоянием между ними.
Геометрический остов или t-остовной граф, или t-остов первоначально был введён как взвешенный граф на множестве точек в качестве вершин, для которого существует t-путь между любой парой вершин для фиксированного параметра t. t-путь определяется как путь в графе с весом, не превосходящим в t раз пространственное расстояние между конечными точками. Параметр t называется коэффициентом растяжения остова.
Граф относительных окрестностей — это неориентированный граф, определённый на множестве точек на евклидовой плоскости путём соединения двух точек p и q ребром, когда не существует третьей точки r, которая ближе как к p, так и q, чем p и q друг к другу. Этот граф предложил Годфрид Туссен в 1980 как способ определения структуры на множестве точек, которая отражает человеческое восприятие формы множества.
Проблема Ружи – Семереди или (6,3)-проблема спрашивает о максимальном числе рёбер в графе, в котором любое ребро принадлежит единственному треугольнику. Эквивалентно, проблема спрашивает о максимальном числе рёбер в сбалансированном двудольном графе, рёбра которого можно разбить на линейное число порождённых паросочетаний, или максимальное число троек, которые можно выбрать из 
точек так, что каждые шесть точек содержат максимум две тройки. Проблема названа именем Имре З. Ружи и Эндре Семереди, которые первыми доказали, что ответ меньше, чем 
на медленно растущий множитель.
Хорда́льный двудо́льный граф — это двудольный граф 
, в котором любой цикл длины по меньшей мере 6 в B имеет хорду, то есть ребро, которое соединяет две вершины, находящиеся на расстоянии > 1. Следовало бы называть эти графы «слабо хордальными и двудольными», поскольку хордальные двудольные графы, вообще говоря, не хордальны, так как могут содержать порождённый путь длины 4.
