Znalezienie podwójnego wykresu

Według książki Topological Graph Theory autorstwa Grossa i Tuckera, biorąc pod uwagę komórkowe osadzenie wykresu na powierzchni (przez „powierzchnię” rozumiem tutaj kulę z pewnymi uchwytami , a poniżej odnosi się do kuli o dokładnie uchwyty), można zdefiniować podwójny multigraf, traktując twarze osadzonego wykresu jako wierzchołki i dodając krawędź między dwoma wierzchołkami dla każdej strony, której odpowiednie ściany mają wspólne na oryginalnym wykresie.S n$n\geq 0$$S_n$$n$

Oto mój problem . Biorąc pod uwagę wykres , muszę znaleźć inny wykres takie, że istnieje powierzchni i komórkową osadzanie na taki, że jest podwójny tego osadzania . Wiem, że istnieje wiele możliwych wykresów ; Muszę tylko znaleźć jeden dla każdego grafu .G ′ S G S G ′ G G ′$G$$G'$$S$$G$$S$$G'$$G$$G'$$G$

Mam kilka pytań . My marki jest do (1) określenia rodzaju o (2) wykrycie osadzania z na , oraz (3) znajdują podwójnego tego wbudowania. Wszystkie te kroki mają znane algorytmy (chociaż (1) jest NP-twardy). Zastanawiam się, czy istnieje sposób na znalezienie który omija obliczenia rodzaju, ponieważ jest to wąskie gardło tego podejścia i to jest moje pierwsze pytanie. Moje drugie pytanie brzmi: jeśli wiem, że jest regularne, czy może to ułatwić obliczenia rodzaju? A moje trzecie pytanie to prośba o wszelkie referencje, które mogą pomóc mi rozwiązać ten problem.G G S n G ′$n$$G$$G$$S_n$$G'$$G$

Czy twój dual musi być z minimalnego rodzaju? Ponieważ znalezienie komorowego osadzenia dla dowolnego wykresu jest banalne: po prostu wybierz uporządkowanie kołowe dla krawędzi przypadających na każdy wierzchołek, dowolnie, a następnie określ ściany osadzania jako sekwencje krawędzi zgodne z wybranymi porządkami.

Podoba mi się przedstawienie GEM (mapa zakodowana w grafie) osadzenia z książki Podstawy teorii wykresów topologicznych autorstwa Benningtona i Little. W tej reprezentacji osadzenie jest reprezentowane przez 3-krawędziowy 3-regularny wykres w kolorze 3 z jednym wierzchołkiem dla każdej flagi osadzenia (trzykrotny przypadek wierzchołka, krawędzi i twarzy) i jedną krawędzią dla dwóch flag różniących się tylko jeden z elementów reprezentowanych przez siebie zestawów wierzchołków / krawędzi / ścian. Na przykład poniższy obraz z Wikipedii można interpretować jako GEM zwykłego dwunastościanu, w którym czerwone cykle reprezentują jego twarze, żółte cykle reprezentują jego krawędzie, a niebieskie cykle reprezentują jego wierzchołki; krawędzie mogą być zabarwione zgodnie z kolorami ich dwóch padających powierzchni.

Biorąc pod uwagę kołowe uporządkowanie krawędzi wykresu G, jego GEM można znaleźć, wykonując cykl 2d wierzchołków dla każdego wierzchołka stopnia d, dwa dla każdej krawędzi, z parami wierzchołków dla każdej krawędzi padającej występującej w cykl w wybranej kolejności kołowej, a następnie dla każdej krawędzi e G łącząc dwie pary krawędzi GEM dla dwóch punktów końcowych e w prostokąt. Jeśli chcesz osadzić orientację, wybór sposobu połączenia tych czterech wierzchołków w prostokąt powinien być zgodny z kolejnością w kole, w przeciwnym razie może być dowolny.

Następnie wierzchołki, krawędzie i ściany osadzania G są reprezentowane przez cykle w GEM, które występują naprzemiennie między dwoma z trzech kolorów krawędzi. Podwójność G jest reprezentowana przez GEM z tym samym bazowym 3-regularnym wykresem, ale z dwoma zamienionymi kolorami krawędzi. A wykres reprezentowany przez GEM można utworzyć, skracając wszystkie jego cykle wierzchołków i łącząc pary równoległych krawędzi w pojedyncze krawędzie. Konstruowanie podwójnego G (o ile nie obchodzi cię, który podwójny) można łatwo wykonać w czasie liniowym.