Algorithme pour la planarisation d'un graphe non-planaire

Question

Existe-t-il un algorithme populaire pour la planarisation d'un graphe non-planaire? Je prévois actuellement de mettre en œuvre un algorithme de disposition planaire orthogonale pour les graphiques non orientés dans Boost (Boost Graph Library). BGL a une implémentation pour vérifier la planarité d'un graphe non orienté (Boyer-Myrvold Planarity Testing) et je prévois d'utiliser l'incrément planaire retourné par cette méthode pour faire une mise en page orthogonale.

Mais je ne suis pas sûr de ce qui devrait être fait si le graphe d'entrée n'est pas planaire. Dois-je faire quelque chose avec le sous-graphique de Kuratowski retourné dans un tel scénario pour rendre le graphique planaire.

Une recherche Google sur "Planarisation de graphes non planaires" renvoie plusieurs articles de recherche. Je ne suis pas sûr de savoir par où commencer.

Answer 1

Il y a exponentiellement beaucoup de sous-graphes $ K_5 $ et $ K_ {3,3} $ d'un $ K_n $, peu importe les mineurs, alors les traiter directement n'est pas terriblement efficace. Je suggère de feuilleter les documents de recherche pour en apprendre un peu plus sur la façon dont les autres personnes abordent le problème. Vous devriez faire attention aux propriétés qui (a) donnent des solutions sensées et (b) ressemblent à des graphiques qui vous intéressent.