Płaska wykres przedstawia wykres, który może być osadzony w płaszczyźnie, bez konieczności przekraczania krawędzie.
Niech będzie - jednolitym hipergraphem, tj. Hipergraphem takim, że wszystkie jego hipergezy mają rozmiar k.k
Wykonano już pewne prace związane z osadzaniem hiperrafatów w płaszczyźnie (w kontekście klastrowania lub innej aplikacji), ale często danych po prostu nie można osadzić w płaszczyźnie. Rozwiązaniem może być albo wymuszenie go, z pewną stratą, albo osadzenie go w wyższym wymiarze, jak sugeruję tutaj:
Naturalne rozszerzenie płaskości (przynajmniej IMO) to „ -proste osadzanie” (czy jest znana inna nazwa?) : embedding , takie, że istnieją powierzchnie, które łączą wszystkie wierzchołki każdego hiperge, i nie przecinają się one z wyjątkiem punktów końcowych.G M : X → R k
(Pomyśl o analogu w 2D, gdzie każda powierzchnia jest krawędzią, którą możesz narysować w dowolny sposób).
Oto przykład prawidłowego 3-prostego osadzenia hipergrrafu 3-jednolitego. (Każdy wierzchołek jest pokolorowany przez zawarte w nim hipergezy, a każda twarz reprezentuje hipersge).
Innym przykładem 3-prostego wykresu jest pełny 3-jednolity hipergraph na 5 wierzchołkach . Aby to zobaczyć, po prostu weź 4 punkty w które nie leżą na płaszczyźnie 2D, utwórz trójkątną piramidę (ich wypukły kadłub) i umieść piąty punkt na środku piramidy, łącząc go z pozostałe wierzchołki.R 3
Podobnie wydaje się, że pełny 3-uniform-hypergraph na 6 wierzchołkach nie ma 3-prostych osadzeń.
Istnieje kilka bardzo przydatnych właściwości grafów płaskich, które umożliwiają ulepszone algorytmy trudnych problemów, gdy wykres jest płaski. Niestety dane często nie są płaskie, choć czasem mają małą wymiarowość. Myślę, że zrozumienie, które właściwości uogólniają wykresy płaskie, pomoże nam dowiedzieć się, które algorytmy można dostosować do wyższego wymiaru za pomocą tego samego narzędzia.
Przykład właściwości, która może być przydatna, pochodzi z twierdzenia Fáry'ego, który sugeruje, że każdy płaski wykres można osadzić w taki sposób, że wszystkie jego krawędzie są segmentami linii prostych.
Czy twierdzenie Fáry'ego ma wyższy wymiar? , tj. jeśli wykres ma osadzenie -proste, to czy ma osadzenie, w którym wszystkie hiper-krawędzie są hiperpłaszczyznami?
Czy są jakieś inne właściwości, które można uogólnić? na przykład, czy Formułę Eulera dla grafów płaskich można w jakiś sposób uogólnić na wyższy wymiar? (chociaż w tej chwili nie jestem pewien, co by to miało znaczyć).