Определение плоскости 3-SAT

Что вас смущает в результатах?

Я вижу разные определения, как некоторые говорят: двудольный граф между предложениями и литералами должен быть плоским (я не знаю под литералами, они означают только x_i или оба x_i и его отрицание, я имею в виду, я не знаю, каковы их График гаджета именно здесь?). Некоторые другие определяют два типа для него: только двудольные ребра между предложениями и литералами или эти плюсы (x_i, ~ x_i). Или кто-то другой говорит, что приведенный выше график плюс (x_i, x_ {i + 1}) 's? Я даже не могу найти оригинальную статью, опубликованную на нем? В принципе, я не могу найти хорошую ссылку с идеальным определением для него?

Первоначальная ссылка: Д. Лихтенштейн, «Плоские формулы и их использование» (1982) ; но есть много небольших вариаций, которые все еще являются NP-полными (доказательство NPC большинства из них легко).

@ Marzio De Biasi Спасибо большое! Но, основываясь на этой паре, планарная 3-SAT - это случай, когда двудольный граф между предложениями о том, что литералы (только x_i не являются их отрицаниями), является плоским. Правильно? Мы можем легко завершить случай, когда мы включаем также отрицание x_i, просто добавив грань между ними, не нарушая планарность, верно?

$x_i$$+x_i$$-x_i$