Definición de Planar 3-SAT

¿Qué te pareció confuso sobre los resultados?

Veo diferentes definiciones, como dicen algunos: el gráfico bipartito entre las cláusulas y los literales debe ser plano (no sé por literales, ¿significan solo x_i o ambos x_i y su negación, quiero decir que no sé cuál es su gráfico de gadget exactamente aquí?). Algunos otros definen dos tipos para ello: solo los bordes bipartitos entre cláusulas y literales, o estos más (x_i, ~ x_i). ¿O algún otro dice, el gráfico anterior más los (x_i, x_ {i + 1})? ¿Ni siquiera puedo encontrar el artículo original publicado en él? Básicamente, ¿no puedo encontrar una buena referencia con una definición perfecta?

La referencia original es: D. Lichtenstein, "Fórmulas planas y sus usos" (1982) ; pero hay muchas pequeñas variaciones que todavía son NP completas (la prueba NPC de la mayoría de ellas es fácil).

@Marzio De Biasi ¡Muchas gracias! Pero, en base a este par, planar 3-SAT es el caso de que el gráfico bipartito entre las cláusulas de que los literales (solo x_i no son sus negaciones) es plano. ¿Derecho? Podemos concluir fácilmente el caso de que incluimos también la negación de x_i simplemente agregando un borde entre ellos, sin perturbar la planaridad, ¿verdad?

$x_i$$+x_i$$-x_i$