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, in which 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, consists of: given a simple graph G, find a planar subgraph of G with the maximum number of edges.
