Satisfiability of co-nested formulas

As a notion dual to Knuth's nested formulas 4], we call a boolean formula in conjunctive normal formco-nested if its clauses can be linearly ordered (sayC={c _i ;i=1,2, ...,n})so that the graphG ^cl =(XC, {xc _i ;xc _i or ¬xc _i } {c _i c _i+1;i=1, 2, ...,n}) allows a noncrossing drawing in the plane so that the circlec ₁,c ₂, ...,c _n bounds the outerface. Our main result is that maximum satisfiability of co-nested formulas can be decided in linear time.Both authors acknowledge a partial support of Ec Cooperative Action IC-1000 (project ALTEC:Algorithms for Future Technologies).