Please use this identifier to cite or link to this item:
|Title:||Removing node overlapping in graph layout using constrained optimization|
|Source:||Marriott, K., Stuckey, P., Tam, V., He, W. (2003). Removing node overlapping in graph layout using constrained optimization. Constraints 8 (2) : 143-171. ScholarBank@NUS Repository. https://doi.org/10.1023/A:1022371615202|
|Abstract:||Although graph drawing has been extensively studied, little attention has been paid to the problem of node overlapping. The problem arises because almost all existing graph layout algorithms assume that nodes are points. In practice, however, nodes may be labelled, and these labels may overlap. Here we investigate how such node overlapping can be removed in a subsequent layout adjustment phase. We propose four different approaches for removing node overlapping, all of which are based on constrained optimization techniques. The first is the simplest. It performs the minimal linear scaling which will remove node-overlapping. The second approach relies on formulating the node overlapping problem as a convex quadratic programming problem, which can then be solved by any quadratic solver. The disadvantage is that, since constraints must be linear, the node overlapping constraints cannot be expressed directly, but must be strengthened to obtain a linear constraint strong enough to ensure no node overlapping. The third and fourth approaches are based on local search methods. The third is an adaptation of the EGENET solver originally designed for solving general constraint satisfaction problems, while the fourth approach is a form of Lagrangian multiplier method, a well-known optimization technique used in operations research. Both the third and fourth method are able to handle the node overlapping constraints directly, and thus may potentially find better solutions. Their disadvantage is that no efficient global optimization methods are available for such problems, and hence we must accept a local minimum. We illustrate all of the above methods on a series of layout adjustment problems.|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Mar 6, 2018
WEB OF SCIENCETM
checked on Jan 23, 2018
checked on Mar 11, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.