Abstract:This paper introduces a crossing elimination model based on a node duplication method and the authors want to minimize the number of duplication. It is related with an artificial problem, called the maximum simple sharing problem. First it is proved to be NP-hard, then a simple greedy algorithm which achieves an approximation factor of 3. Next the maximum disjoint simple sharing problem is introduced, which is naturally a 2-approximation of the maximum simple sharing problem, and the paper shows that this problem can be solved optimally by reducing to the perfect matching problem in a series of carefully constructed graphs. At last, the approximation factor is further improved to 12/7 with a local search technique.