Nesting software optimizes material yield, but if the parts cannot be cut efficiently, ensuring part quality and increased the throughput, the savings gained in material efficiency are lost. Based on graph theory, the mathematical model of nozzle path planning problem for the laser cutting of the edge-shared nested regular or irregular parts is established in this paper. The optimization objective of the problem is defined as minimum pierce points and shortest vacant path of nozzle in edge-shared cutting, which includes machining quality, efficiency and manufacturing cost. Three algorithms to solve the problem are presented that can meet the laser cutting technics. The first algorithm is a new Eulerian trail algorithm to solve the problem under ideal circumstances, The second algorithm uses the algorithm based on the minimum weight and maximum matching algorithms of complete graph with the vertices of odd degree to solve the problem under general circumstances, The third algorithm uses the scrap areas to investigate further reduction in the number of pierce points. Every sort of application instance of the three algorithms mentioned is presented and their validity is testified.