Patent ID: 7266799

Claim:
A Steiner tree handling device which handles a Steiner tree constituted by plural horizontal or vertical edges connecting plural nodes, comprising: a Steiner tree obtaining unit which obtains a Steiner tree having at least one shape; a Steiner tree deformation unit which deforms the obtained Steiner tree into a Steiner tree having a different shape without changing the size of the obtained Steiner tree; a dependency graph creation unit which creates a dependency graph by determining dependency as to whether slides of each edge depend on slides of other edges or not, when the Steiner tree deformation unit performs the deformation; an independent slide group determination unit which determines a group of independently slidable edges, based on the graph created by the dependency graph creation unit; and a partial variation calculation unit which, if an edge of the Steiner tree moves in a predetermined range, calculates a number of deformed variations on the Steiner tree that includes the edge moving, based on a determination result from the independent slide group determination unit.