File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Removing node overlapping in graph layout using constrained optimization

TitleRemoving node overlapping in graph layout using constrained optimization
Authors
KeywordsConstrained Optimization
Disjunctive Constraints
Graph Layout
Issue Date2003
PublisherSpringer New York LLC. The Journal's web site is located at http://springerlink.metapress.com/openurl.asp?genre=journal&issn=1383-7133
Citation
Constraints, 2003, v. 8 n. 2, p. 143-171 How to Cite?
AbstractAlthough 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.
Persistent Identifierhttp://hdl.handle.net/10722/155185
ISSN
2015 Impact Factor: 0.622
2015 SCImago Journal Rankings: 0.477
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorMarriott, Ken_US
dc.contributor.authorStuckey, Pen_US
dc.contributor.authorTam, Ven_US
dc.contributor.authorHe, Wen_US
dc.date.accessioned2012-08-08T08:32:14Z-
dc.date.available2012-08-08T08:32:14Z-
dc.date.issued2003en_US
dc.identifier.citationConstraints, 2003, v. 8 n. 2, p. 143-171en_US
dc.identifier.issn1383-7133en_US
dc.identifier.urihttp://hdl.handle.net/10722/155185-
dc.description.abstractAlthough 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.en_US
dc.languageengen_US
dc.publisherSpringer New York LLC. The Journal's web site is located at http://springerlink.metapress.com/openurl.asp?genre=journal&issn=1383-7133en_US
dc.relation.ispartofConstraintsen_US
dc.subjectConstrained Optimizationen_US
dc.subjectDisjunctive Constraintsen_US
dc.subjectGraph Layouten_US
dc.titleRemoving node overlapping in graph layout using constrained optimizationen_US
dc.typeArticleen_US
dc.identifier.emailTam, V:vtam@eee.hku.hken_US
dc.identifier.authorityTam, V=rp00173en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1023/A:1022371615202en_US
dc.identifier.scopuseid_2-s2.0-0037382018en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-0037382018&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume8en_US
dc.identifier.issue2en_US
dc.identifier.spage143en_US
dc.identifier.epage171en_US
dc.identifier.isiWOS:000220241700002-
dc.publisher.placeUnited Statesen_US
dc.identifier.scopusauthoridMarriott, K=7005317835en_US
dc.identifier.scopusauthoridStuckey, P=7006033659en_US
dc.identifier.scopusauthoridTam, V=7005091988en_US
dc.identifier.scopusauthoridHe, W=7402007605en_US
dc.identifier.citeulike1714713-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats