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

Межі розмірів універсальної множини точок

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

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

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

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

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

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

Інші способи малювання

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

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

Примітки

Література

. Див., зокрема, задачу 11 на стор. 520.