Fixed-point logics on planar graphs
Martin Grohe · 2002
We study the expressive power of inflationary fixed-point logic IFP and inflationary fixed-point logic with counting IFP+C on planar graphs. We prove the following results: (1) IFP captures polynomial time on 3-connected planar graphs, and IFP+C captures polynomial time on arbitrary planar graphs. (2) Planar graphs can be characterized up to isomorphism in a logic with finitely many variables and counting. This answers a question of Immerman (1987). (3) The class of planar graphs is definable in IFP. This answers a question of Dawar and Gradel.