Kombinatoryczne osadzanie wykresu

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)?

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/ .