Circuit Complexity of Properties of Graphs with Constant Planar Cutwidth

We study the complexity of several of the classical graph decision problems in the setting of bounded cutwidth and how imposing planarity affects the complexity. We show that for 2-coloring, for bipartite perfect matching, and for several variants of disjoint paths the straightforward NC1 upper bound may be improved to AC0[2], ACC0, and AC0 respectively for bounded planar cutwidth graphs. We obtain our upper bounds using the characterization of these circuit classes in tems of finite monoids due to Barrington and Thérien. On the other hand we show that 3-coloring and Hamilton cycle remain hard for NC1 under projection reductions, analogous to the NP-completeness for general planar graphs. We also show that 2-coloring and (non-bipartite) perfect matching are hard under projection reductions for certain subclasses of AC0[2]. In particular this shows that our bounds for 2-coloring are quite close.