The Efficient Recognition on Net-extensibility of Graphs
刘彦佩 · Chinese Science Bulletin · 1993
According to [1], recognizing the net-embeddability of a graph is a very hard problem. Up to now, no efficient algorithm has been known. However, this note presents a theoretical account for recognizing the net-embeddability of a graph more efficiently when the number of splitting pairs of vertices is small enough compared with the order of the graph. In fact, it is shown in this note that efficient algorithms for recognizing the net-extensibility and finding a net-extension of a planar embedding of a graph can be established.