Graph planarity definability clarification in literature?

Question

Here it says planarity is definable in first order.

http://jgaa.info/accepted/recent/Brandenburg.pdf

Here it says planarity testing of graphs is not a first order property.

Refer https://simons.berkeley.edu/sites/default/files/docs/5233/lecture22.pdf

Which of this is true?

1. Is planarity definable in first order?

2. If not what is the right way to define planarity in presburger?

Answer 1

The two claims do not contradict.

Brandenburg's paper deals with "topological graphs": graphs drawn in the plane. Here, there is a built-in predicate $\chi(e,f)$ which is true if and only if edges $e$ and $f$ cross. Using this predicate, it is easy to determine if a graph drawing is a plane embedding: $\chi(e,f)$ must be false for all pairs of edges. (So, in other words, $\forall e\, \forall f\, \neg \chi(e,f)$.)

Note that even if a topological graph is non-planar, the underlying graph may still be planar, just badly drawn. For example, the graph below is planar, but the drawing is not, so Brandenburg considers this a nonplanar topological graph:

(Of course, if a graph is nonplanar, then any drawing of it will have crossings, so it will also be nonplanar as a topological graph.)

The model theory lecture, on the other hand, is actually talking about graphs, and does not have the luxury of a predicate $\chi$.