Диаграмма Вороного конечного множества точек S на плоскости представляет такое разбиение плоскости, при котором каждая область этого разбиения образует множество точек, более близких к одному из элементов множества S, чем к любому другому элементу множества.
В теории графов графом единичных кругов называется граф пересечений семейства единичных кругов на евклидовой плоскости. То есть мы образуем вершину для каждого круга и соединяем две вершины ребром, если соответствующие круги пересекаются.
В теории графов графом единичных расстояний называется граф, образованный точками на евклидовой плоскости, при этом две вершины соединяются ребром, если расстояние между ними равно в точности единице. Рёбра графа единичных расстояний иногда пересекаются, так что они не всегда планарны. Граф единичных расстояний без пересечений называется спичечным графом.
Веретено Мозера — неориентированный граф, названный в честь математиков Лео Мозера и его брата Вильяма, имеющий семь вершин и одиннадцать рёбер. Он является графом единичных расстояний, требующим четыре цвета в любой раскраске, и его существование используется для доказательства того, что хроматическое число плоскости равно по меньшей мере четырём.
Конфигурацией Мёбиуса или тетраэдрами Мёбиуса называется конфигурация в евклидовом пространстве или проективном пространстве, состоящая из двух взаимно вписанных тетраэдров — каждая вершина одного тетраэдра лежит на плоскости, проходящей через грань другого тетраэдра и наоборот. Таким образом, в результирующей системе восьми точек и восьми плоскостей каждая точка лежит на четырёх плоскостях, и каждая плоскость содержит четыре точки.
В теории графов кограф, или дополнительно сводимый граф, или граф, свободный от P4, — это граф, который можно получить из графа с единственной вершиной K1 путём операций дополнения и объединения графов. Таким образом, семейство кографов — это наименьший класс графов, содержащий K1 и замкнутый относительно дополнения и объединения.
Древесность неориентированного графа — это минимальное число лесов, на которые можно разложить рёбра. Эквивалентно это является минимальным числом остовных деревьев, которые необходимы для покрытия рёбер графа.
Граф ближайших соседей (ГБС) для множества P, состоящего из n объектов в метрическом пространстве — это ориентированный граф, вершинами которого служат элементы множества P, в котором существует ориентированное ребро из p в q, если q является ближайшим соседом p.
k-Вырожденный граф — это неориентированный граф, в котором каждый подграф имеет вершины со степенью, не превосходящей k. Вырожденность графа — это наименьшее значение k, для которого граф является k-вырожденным. Вырожденность графа отражает, насколько граф разрежен и отражает другие меры разреженности, такие как древесность графа.
Евклидово минимальное остовное дерево — это минимальное остовное дерево набора из n точек на плоскости, где вес ребра между любой парой точек является евклидовым расстоянием между двумя точками. Простыми терминами, EMST связывает набор точек с помощью отрезков так, что общая длина всех отрезков минимальна и любая точка может быть достигнута из другой точки по этим отрезкам.
Геометрический остов или t-остовной граф, или t-остов первоначально был введён как взвешенный граф на множестве точек в качестве вершин, для которого существует t-путь между любой парой вершин для фиксированного параметра t. t-путь определяется как путь в графе с весом, не превосходящим в t раз пространственное расстояние между конечными точками. Параметр t называется коэффициентом растяжения остова.
Книга может быть любым графом некоторого вида, который образован циклами, имеющими общее ребро.
Граф относительных окрестностей — это неориентированный граф, определённый на множестве точек на евклидовой плоскости путём соединения двух точек p и q ребром, когда не существует третьей точки r, которая ближе как к p, так и q, чем p и q друг к другу. Этот граф предложил Годфрид Туссен в 1980 как способ определения структуры на множестве точек, которая отражает человеческое восприятие формы множества.
Альфа-форма или 
-форма — это семейство кусочно-линейных простых кривых на евклидовой плоскости, ассоциированных с формой конечного множества точек. Альфа-формы первым определили Эдельсбруннер, Киркпатрик и Зайдель. Альфа-форма, ассоциированная с множеством точек, является обобщением концепции выпуклой оболочки, то есть любая выпуклая оболочка является альфа-формой, но не любая альфа-форма является выпуклой оболочкой.
Граф Уркхарта множества точек на плоскости, названный в честь Родерика Б. Уркхарта, получается путём удаления самого длинного ребра из каждого треугольника в триангуляции Делоне.
Модель Эрдёша — Реньи — это одна из двух тесно связанных моделей генерации случайных графов. Модели названы именами математиков Пала Эрдёша и Альфреда Реньи, которые первыми представили одну из моделей в 1959 году, в то время как Эдгар Гильберт предложил другую модель одновременно и независимо от Эрдёша и Реньи. В модели Эрдёша и Реньи все графы с фиксированным набором вершин и фиксированным набором рёбер одинаково вероятны. В модели, предложенной Гильбертом, каждое ребро имеет фиксированную вероятность присутствия или отсутствия, независимую от других рёбер. Эти модели можно использовать в вероятностном методе для доказательства существования графов, удовлетворяющих различным свойствам или для обеспечения точного определения, это для свойства понимается, что оно выполняется для почти всех графов.
