An evolutionary formulation of the crossing number problem

DOI10.1155/2009/154015MaRDI QIDQ1040098zbMATH OpenOpenAlexWikidataFDO

Authors Che Sheng Gan, Wee Chiat Alan Tan, Voon Chet Koo, Kwang Hwai Mak

Publication date 23 November 2009

Published in Discrete Dynamics in Nature and Society (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://eudml.org/doc/222766

zbMATH Keywords

complete graphscrossing numberEAevolutionary algorithmgraph drawing algorithmminimum crossings

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)

Review text

Summary: A graph drawing algorithm is presented which results in complete graphs having minimum crossings equal to that of Guy's conjecture. It is then generalized and formulated in an evolutionary algorithm (EA) to perform constrained search for the crossing numbers. The main objective of this work is to present a suitable two-dimensional scheme which can greatly reduce the complexity of finding crossing numbers by using computer. Program performance criteria are presented and discussed. It is shown that the EA implementation provides good confirmation of the predicted crossing numbers.

Recommendations

• scientific article; zbMATH DE number 1109408
• An algorithmic development to minimize crossings in electronic circuits
• Graph Drawing
• Recent advances in exact crossing minimization (extended abstract)
• scientific article; zbMATH DE number 2170413

Cites work

• Crossing Number is NP-Complete
• Graph Drawing
• scientific article; zbMATH DE number 871167 (Why is no real title available?)
• scientific article; zbMATH DE number 3394160 (Why is no real title available?)
• The crossing number of K₁₁ is 100
• Toward a theory of crossing numbers

Cited in

(2)

• Exact solution for the boundary-crossing problem in genetic mapping experiment
• Number of cycles in evolutionary operation

This page was built for publication: An evolutionary formulation of the crossing number problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1040098)