ABSTRACT
In graph theory, questions related to planarity always played an important role. The main subject of this chapter is the following problem, which is denoted here as MAXIMUM-WEIGHT PLANAR SUBGRAPH: Given a graph G with a nonnegative weight defined for each edge, find a planar subgraph of G of maximum weight, where the weight of a subgraph is simply the sum of the weights of the edges in the subgraph. Its unweighted version, denoted as MAXIMUM PLANAR SUBGRAPH, is: given a simple graph G , find a planar subgraph of G with the maximum number of edges.
