Barzilai-Borwein Method in Graph Drawing Algorithm Based on Kamada-Kawai Algorithm

0472759 - ÚGN 2017 RIV US eng C - Konferenční příspěvek (zahraniční konf.)
Hasal, Martin - Pospíšil, L. - Nowakova, J.
Barzilai-Borwein Method in Graph Drawing Algorithm Based on Kamada-Kawai Algorithm.
International Conference of Numerical Analysis and Applied Mathematics 2015 (ICNAAM 2015). New York: AIP Publishing, 2016 - (Simos, T.; Tsitouras, C.), č. článku 360005. AIP Conference Proceedings, 1738. ISBN 978-0-7354-1392-4. ISSN 0094-243X.
[ICNAAM 2015 - International Conference on Numerical Analysis and Applied Mathematics. Rhodos (GR), 23.09.2015-29.09.2015]
Institucionální podpora: RVO:68145535
Klíčová slova: undirected graphs * Kamada-Kawai algorithm * Barzilai-Borwein method
Kód oboru RIV: BA - Obecná matematika
http://aip.scitation.org/doi/pdf/10.1063/1.4952138

Extension of Kamada-Kawai algorithm, which was designed for calculating layouts of simple undirected graphs, is presented in this paper. Graphs drawn by Kamada-Kawai algorithm exhibit symmetries, tend to produce aesthetically pleasing and crossing-free layouts for planar graphs. Minimization of Kamada-Kawai algorithm is based on Newton-Raphson method, which needs Hessian matrix of second derivatives of minimized node. Disadvantage of Kamada-Kawai embedder algorithm is computational requirements. This is caused by searching of minimal potential energy of the whole system, which is minimized node by node. The node with highest energy is minimized against all nodes till the local equilibrium state is reached. In this paper with Barzilai-Borwein (BB) minimization algorithm, which needs only gradient for minimum searching, instead of Newton-Raphson method, is worked. It significantly improves the computational time and requirements.
Trvalý link: http://hdl.handle.net/11104/0269989