Paper: Fixed-Point Logics on Planar Graphs (at LICS 1998)

Authors: Martin Grohe

Abstract

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

BibTeX

  @InProceedings{Grohe-FixedPointLogicsonP,
    author = 	 {Martin Grohe},
    title = 	 {Fixed-Point Logics on Planar Graphs},
    booktitle =  {Proceedings of the Thirteenth Annual IEEE Symposium on Logic in Computer Science (LICS 1998)},
    year =	 {1998},
    month =	 {June}, 
    pages =      {6--15},
    location =   {Indianapolis, IN, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }