Witam
Potrzebuję jakiegoś mądrego sposobu sprawdzenia czy graf jest mapą (grafem planarnym, spójnym bez mostów). Póki co widzę dwie ścieżki:
- sprawdzenie spójności grafu, istnienia mostów oraz podgrafu K3,3 lub K5
- próba pokolorowania grafu dualnego na maks 4 kolory
W pierwszym podejściu nie wiem jak znaleźć podgrafy K3,3 lub K5, w drugim natomiast jak znaleźć graf dualny. Stąd prośba o wskazówki lub jakieś inne rozwiązania.
Pozdrawiam