The efficient recognition on net-extensibility of graphs (Q687910): Difference between revisions

Let \(\mu(G)\) be an embedding of \(G\) in the plane. A net-extension of \(\mu(G)\) is an embedding of \(G\) which is topologically equivalent to \(\mu(G)\) where the vertices are integer grid points and the edges are either horizontal or vertical paths. The author gives an algorithm for determining when an embedding \(\mu(G)\) has a net-extension. The algorithm develops a system of equations which records the angles of the desired net-extension, then translates these equations to a transportation problem.