Kombinatoryczne osadzanie wykresu

12

Tutaj: http://www.planarity.org/Klein_elementary_graph_theory.pdf (w osadzeniach rozdziałów) podano definicję kombinatorycznego osadzania wykresu płaskiego. (z definicją ścian i tak dalej) Choć można go łatwo zastosować do dowolnego wykresu, definiują wykres płaski jako wykres, dla którego obowiązuje formuła Eulera (zakładając, że wykres jest połączony). Zrozumiałe jest, że dla każdego wykresu płaskiego definicja ścian w osadzaniu kombinatorycznym jest podobna do definicji ścian w osadzaniu topologicznym. (zakładając, że wykres jest połączony. W przeciwnym razie w osadzaniu kombinatorycznym będziemy mieli nieskończoną powierzchnię dla każdego podłączonego komponentu)

Pytanie brzmi: jeśli dla jakiegoś połączonego grafu jego osadzanie kombinatoryczne spełnia formułę Eulera, czy to oznacza, że ​​wykres ten jest płaski w sensie topologicznym (ma osadzanie płaskie, tj. Jest to płaski wykres)?

Fiński
źródło
W dalszej części tego artykułu udzielają odpowiedzi, że jest to możliwe. Ale czy ktoś może podać linki do dowodu?
Finsky,

Odpowiedzi:

16

To naprawdę mniej dotyczy samego wykresu, a więcej topologii. Osadzanie kombinatoryczne definiuje 2-różnorodną przestrzeń topologiczną, w której każdy punkt ma sąsiedztwo homeomorficzne z 2-wymiarowym otwartym dyskiem: osadzanie umożliwia zdefiniowanie powierzchni, a my możemy zdefiniować przestrzeń topologiczną, wybierając dysk dla każdego twarz i sklejając je razem wzdłuż krawędzi wykresu. Dobrze znane twierdzenie w topologii (zwane klasyfikacją 2-rozmaitości) mówi nam dokładnie, które 2-rozmaitości są możliwe i wszystkie można je od siebie odróżnić, czy są orientowalne lub czy mają tę samą charakterystykę Eulera (lub oba ) - patrz http://www.maths.ed.ac.uk/~aar/surgery/zeeman.pdfdla niektórych uzasadnionych notatek z wykładu na ten temat, które zawierają dowód, o który prosisz. W tej klasyfikacji nie ma innych 2-rozmaitości, które mają tę samą charakterystykę Eulera co kula, więc jeśli obliczysz charakterystykę Eulera i stwierdzisz, że pasuje ona do wzoru dla kuli, wiesz, że twoje osadzenie musi być na kuli.

Znalezienie osadzenia z rzeczywistymi współrzędnymi geometrycznymi w płaszczyźnie, gdy już masz płaskie osadzenie kombinatoryczne, nie jest całkowicie trywialne, ale można to zrobić np. Przy użyciu teorii lasu Schnydera. Na przykład mam kilka notatek z wykładów na stronie http://www.ics.uci.edu/~eppstein/gina/schnyder/ .

David Eppstein
źródło
Dziękuję bardzo za tak obszerną odpowiedź! Przeczytałem pierwszy artykuł i wygląda na to, że zrozumiałem dowód. Pozostało mi jednak jedno pytanie: czy to wszystko oznacza, że ​​jeśli zdefiniujemy powierzchnie, co nam się podoba (mam na myśli dowolny podzbiór krawędzi, a nie jak w kombinatorycznym osadzaniu z porządkiem i innymi rzeczami przeciwnie do ruchu wskazówek zegara), skleimy je wszystkie w taki sposób, aby klej jest tylko na współdzieleniu krawędzi 2 powierzchni, zdefiniuj powstałe „sęki” w punktach końcowych krawędzi jako wierzchołki ORAZ jeśli formuła Eulera się utrzymuje, czy jest to wykres płaski?
Finsky,
1
Trzeba uważać, aby uzyskać rozmaitość: powierzchnie osadzania powinny być dyskami topologicznymi, nie wolno pozostawiać nieoczywistych krawędzi, każda krawędź powinna być przyklejona tylko do drugiej krawędzi, a na każdym wierzchołku powinno być tylko jeden cykl krawędzi i twarzy przyklejonych wokół niego (nie tak, jak dostajesz, jeśli skleisz dwa stożki razem na ich końcach). Musisz także zacząć od podłączonego wykresu lub policzyć charakterystykę Eulera dla każdego komponentu osobno. Ale jeśli wszystko to jest prawdą, a formuła Eulera obowiązuje, to tak, to jest planarna.
David Eppstein,
Tak, zapomniałem o tych sprawach, na pewno oni też muszą to wytrzymać. Dziękuję Ci bardzo!
Finsky,