Définition de Planar 3-SAT

Qu'est-ce qui vous a dérouté dans les résultats?

Je vois différentes définitions, comme certains le disent: le graphe biparti entre les clauses et les littéraux doit être planaire (je ne sais pas par littéraux signifient-ils seulement x_i ou les deux x_i et sa négation, je veux dire, je ne sais pas quel est leur gadget graphique exactement ici?). Certains autres lui définissent deux types: uniquement les arêtes bipartites entre les clauses et les littéraux, ou ces plus (x_i, ~ x_i). Ou un autre dit, le graphique ci-dessus plus les (x_i, x_ {i + 1})? Je ne trouve même pas le papier original publié dessus? En gros je ne trouve pas une bonne référence avec une définition parfaite pour ça?

La référence d'origine est: D. Lichtenstein, "Les formules planaires et leurs utilisations" (1982) ; mais il existe de nombreuses petites variations qui sont toujours NP-complètes (la preuve NPC de la plupart d'entre elles est facile).

@Marzio De Biasi Merci beaucoup! Mais, basé sur ce paer, planaire 3-SAT est le cas que le graphe bipartite entre les clauses que les littéraux (seulement x_i ne sont pas leurs négations) est planaire. Droite? Nous pouvons facilement conclure le cas que nous incluons également la négation des x_i simplement en ajoutant un bord entre eux, sans perturber la planarité, non?

$x_i$$+x_i$$-x_i$