Maximum weighted induced bipartite subgraphs and acyclic subgraphs of planar cubic graphs

Abstract

We study the maximum node-weighted induced bipartite subgraph problem in planar graphs with maximum degree three. We show that this is polynomially solvable. It was shown in Choi, Nakajima, and Rim [SIAM J. Discrete Math., 2 (1989), pp. 38{47] that it is NP-complete if the maximum degree is four. We extend these ideas to the problem of balancing signed graphs. We also consider maximum weighted induced acyclic subgraphs of planar directed graphs. If the maximum degree is three, it is easily shown that this is polynomially solvable. We show that for planar graphs with maximum degree four the same problem is NP-complete.