I want to know whether a certain graph problem is NP-complete or not. The problem is as follows.
Given an undirected planar bipartite graph with in every vertex a number. Can you make a subgraph for which the degree of every vertex is equal to the corresponding number?
Does anyone have an idea whether this problem is NP-complete, or know a related problem?