ScholarBank@NUShttps://scholarbank.nus.edu.sgThe DSpace digital repository system captures, stores, indexes, preserves, and distributes digital research material.Tue, 29 Nov 2022 11:40:34 GMT2022-11-29T11:40:34Z5021Removing node and edge overlapping in graph layouts by a modified EGENET solverhttps://scholarbank.nus.edu.sg/handle/10635/40139Title: Removing node and edge overlapping in graph layouts by a modified EGENET solver
Authors: Tam, Vincent
Abstract: Graph layout problems such as node and edge overlapping occur widely in many industrial computer-aided design applications. Usually, these problems are handled in an ad hoc manner by some specially designed algorithms. GENET and its extended model EGENET are local search methods used to solve constraint satisfaction problems such as the car-sequencing problems efficiently. Both models use the min-conflict heuristic to update every finite-domain variable for finding local minima, and then apply heuristic learning rule(s) to escape the local minima not representing solution(s). In the past, few researchers have ever considered to apply any local search method like the EGENET approach to solve graph layout problems. In this paper, we consider how to modify the original EGENET model for solving the graph layout problems formulated as continuous constrained optimization problems. The empirical evaluation of different approaches on the graph layout problems demonstrated some advantages of our modified EGENET approach, which requires further investigation. More importantly, this interesting proposal opens up numerous opportunities for exploring the other possible ways to modify the original EGENET model, or using the other local search methods to solve these graph layout problems.
Fri, 01 Jan 1999 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/401391999-01-01T00:00:00ZRemoving node overlapping in graph layout using constrained optimizationhttps://scholarbank.nus.edu.sg/handle/10635/39028Title: Removing node overlapping in graph layout using constrained optimization
Authors: Marriott, K.; Stuckey, P.; Tam, V.; He, W.
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.
Wed, 01 Jan 2003 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/390282003-01-01T00:00:00Z