GA for straight-line grid drawings of maximal planar graphs
作者： Mohamed A. El-Sayed
DOI: 10.1016/J.EIJ.2012.01.003
关键词:
摘要: Abstract A straight-line grid drawing of a planar graph G n vertices is on an integer such that each vertex drawn as point and edge segment without crossings. Finding algorithms for drawings maximal graphs (MPGs) in the minimum area still elusive goal. In this paper we explore potential use genetic to problem various implementation aspects related it. Here introduce algorithm, which nicely draws MPG moderate size. This new algorithm these rectangular with ⌊ 2 ( - 1 ) / 3 ⌋ × at least, optimal (proved mathematically). Also, novel issue proposed method fitness evaluation method, less costly than standard procedure. It described, tested several MPG.
core.ac.uk
elsevier.com
sci-hub.se 参考文章(39)
Peter Eades, Robert F. Cohen, Mao Lin Huang, Online Animated Graph Drawing for Web Navigation graph drawing. pp. 330- 335 ,(1997) , 10.1007/3-540-63938-1_77
Bruno Pinaud, Pascale Kuntz, RØmi Lehn, Dynamic Graph Drawing with a Hybridized Genetic Algorithm Adaptive Computing in Design and Manufacture VI. pp. 365- 375 ,(2004) , 10.1007/978-0-85729-338-1_31
Janet M. Six, Ioannis G. Tollis, A Framework for Circular Drawings of Networks graph drawing. pp. 107- 116 ,(1999) , 10.1007/3-540-46648-7_11
Cezary Z. Janikow, Zbigniew Michalewicz, Lindsay J. Groves, Paul V. Elia, Genetic algorithms for drawing directed graphs Methodologies for intelligent systems, 5. pp. 268- 276 ,(1991)
Michael Farrugia, Aaron Quigley, Effective temporal graph layout: a comparative study of animation versus static display methods Information Visualization. ,vol. 10, pp. 47- 64 ,(2011) , 10.1057/IVS.2010.10
Bentley, Ottmann, Algorithms for Reporting and Counting Geometric Intersections IEEE Transactions on Computers. ,vol. 28, pp. 643- 647 ,(1979) , 10.1109/TC.1979.1675432
Dorothea Wagner, Michael Kaufmann, Drawing graphs: methods and models Drawing graphs: methods and models. pp. 312- 312 ,(2001)
Goos Kant, Xin He, Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems Theoretical Computer Science. ,vol. 172, pp. 175- 193 ,(1997) , 10.1016/S0304-3975(95)00257-X
H.C Purchase, Effective information visualisation: A study of graph drawing aesthetics and algorithms Interacting with Computers. ,vol. 13, pp. 147- 162 ,(2000) , 10.1016/S0953-5438(00)00032-1
Walter Schnyder, Embedding planar graphs on the grid symposium on discrete algorithms. pp. 138- 148 ,(1990) , 10.5555/320176.320191