Універсальна множина точок

Універсальна множина точок порядку n — це множина S точок евклідової площини з властивістю, що будь-який планарний граф з n вершинами має малюнок із прямими ребрами, в якому всі вершини розташовуються в точках множини S.

Якщо n не перевищує 10, існує універсальна множина точок, що має рівно n точок, але для всіх n ≥ 15 знадобляться додаткові точки^[1].

Деякі автори показали, що підмножина цілої ґратки розміру O(n) × O(n) є універсальною. Зокрема, Фрейсікс, Пах і Поллак^[2] показали, що ґратка (2n − 3) × (n − 1) є універсальною, а Шнайдер^[3] зменшив до трикутної підмножини ґратки (n − 1) × (n − 1) з n²/2 − O(n) точками. Модифікуючи метод Фрейсікса, Паха і Шнайдера, Бранденбург^[4] знайшов вкладення будь-якого планарного графа в трикутну підмножину ґратки, що містить 4n²/9 точок. Універсальна множина точок у вигляді прямокутної ґратки повинна мати розмір щонайменше n/3 × n/3^[5], але це виключає можливість існування меншої універсальної множини точок інших типів. Найменші відомі універсальні множини точок не засновані на ґратках, а будуються зі суперсхем^[en] (перестановок, що містять усі образи перестановок^[en] заданого розміру). Універсальні множини точок, побудовані так, мають розмір n²/4 − O(n)^[6].

Фрейсікс, Пах і Поллак^[2] довели першу нетривіальну нижню межу розміру універсальної множини точок у вигляді n + Ω(√n), а Кробак і Карлофф^[7] показали, що універсальна множина точок має містити щонайменше 1.098n − o(n) точок. Куровскі^[8] запропонував навіть сильнішу межу 1.235n − o(n), яка залишається кращою нижньою межею^[9].

Закриття проміжку між відомими лінійними межами та квадратичними верхніми межами залишається відкритою проблемою^[10].

Підкласи планарних графів можуть, у загальному випадку, мати менші універсальні множини (множини точок, які дозволяють малювання всіх графів підкласу з n вершинами з прямими ребрами), ніж повний клас усіх планарних графів, і в багатьох випадках існують універсальні множини точок, що мають рівно n точок. Наприклад, нескладно бачити, що будь-яка множина з n точок у опуклій позиції^[en] (які служать вершинами опуклого многокутника), є універсальною для n вершинних зовніпланарних графів, і, зокрема, для дерев. Менш очевидно, що будь-яка множина з n точок у загальному положенні (ніякі три не лежать на одній прямій) залишається універсальною для зовніпланарних графів^[11].

Планарні графи, які можна розбити на вкладені цикли, та планарні графи з обмеженою шляховою шириною мають універсальну множину точок майже лінійного розміру^[12][6]. Планарні 3-дерева мають універсальні множини точок розміру O(n^5/3). Та сама межа існує для паралельно-послідовних графів^[13].

Як і в разі малювання графів із прямими ребрами, універсальні множини точок вивчалися для інших способів малювання. У більшості випадків існують універсальні множини точок, що мають рівно n точок, і ґрунтуються вони на топологічному книжковому вкладенні, в якому вершини розташовуються на прямій на площині, а ребра малюються як криві, які перетинають цю лінію максимум один раз. Наприклад, будь-яка множина n колінеарних точок є універсальною для дугової діаграми, в якій кожне ребро подано або як одне півколо, або як гладка крива, утворена двома півколами^[14].

Можна показати, що за використання подібного розташування будь-яка опукла крива на площині містить підмножину з n точок, що є універсальною для малюнків у вигляді ламаних із максимум одним зламом на ребро^[15]. Ця множина містить тільки вершини малюнка, але не точки зламу. Відомі великі множини, які можна використовувати для малюнків за допомогою ламаних, у яких вершини і всі точки зламу є точками множини^[16].