Плоский граф представляет собой график , который может быть встроен в плоскости, без пересечения ребер.
Пусть будет к -равномерному-Гиперграфу, т.е. гиперграфа, что вся его гиперребра имеет размер к.
Была проделана некоторая работа по встраиванию гиперграфов в плоскость (в контексте кластеризации или какого-либо другого приложения), но часто данные просто не могут быть встроены в плоскость. Решением может быть либо заставить его с некоторой потерей, либо встроить его в более высокое измерение, как я предлагаю здесь:
Естественным расширением планарности (по крайней мере IMO) является « простое вложение» (есть ли другое известное название для него?) В G : вложение M : X → R k , такое, что существуют поверхности, которые соединяют все вершины каждого гипергиба, и они не пересекаются, за исключением конечных точек.
(Подумайте об аналоге в 2D, где каждая поверхность - это край, который вы можете нарисовать так, как вам нравится).
Вот пример правильного 3-простого вложения 3-равномерного гиперграфа. (Каждая вершина окрашена гиперэгезиями, в которых она содержится, и каждая грань представляет гиперэдж).
Другим примером 3-простого графа является полный 3-равномерный гиперграф на 5 вершинах . Чтобы увидеть это, просто возьмите 4 точки в R 3, которые не лежат на 2D-плоскости, создайте треугольную пирамиду (их выпуклый корпус) и поместите пятую точку в центре пирамиды, соединяя ее с другими вершинами.
Точно так же кажется, что полный 3-равномерный гиперграф на 6 вершинах не имеет 3-простого вложения.
Есть несколько очень полезных свойств плоских графов, которые позволяют улучшить алгоритмы для сложных задач, когда граф плоский. К сожалению, данные часто не являются плоскими, хотя иногда они имеют низкую размерность. Я думаю, что понимание того, какие свойства плоских графов обобщаются, поможет нам выяснить, какие алгоритмы можно адаптировать для более высокой размерности с помощью того же инструмента.
Примером свойства, которое может быть полезно, является теорема Фари, которая предполагает, что каждый планарный граф может быть встроен таким образом, что все его ребра являются отрезками прямых линий.
Есть ли другие свойства, которые можно обобщить? например, можно ли как-нибудь обобщить формулу Эйлера для плоских графов на более высокую размерность? (хотя на данный момент я не уверен, что бы это означало).