Two new criteria for finding Steiner hulls in Steiner tree problems (Q1186803)

Let \(G=(V,E)\) be a planar graph with non-negative edge weights and let \(K\) be a given subset of \(V\). The Steiner tree problem on graphs is that of finding a tree of minimum length in \(G\) containing all vertices of \(K\). A Steiner hull for \(K\) is a subgraph of \(G\) which is known to contain a Steiner tree for \(K\). Using path-convex envelopes a new criterion for finding Steiner hulls is given which strengthens known polynomial-time methods of finding Steiner hulls. Similar work is done for the rectilinear Steiner tree problem which consists in the search for a shortest network interconnecting a given set \(K\) of points in the Euclidean plane where only horizontal or vertical line segments are allowed. Here a subregion is described which is known to contain a Steiner tree for \(K\).