摘要: The author introduces a method to optimize the required area, minimum angle and number of bends planar drawings graphs on grid. main tool is new type ordering vertices faces triconnected graphs. With this linear time space algorithms can be designed for many graph drawing problems. He shows that every G drawn convexly with straight lines an (2n-4)*(n-2) If has maximum degree four (three), then orthogonal at most (/sup 3n///sub 2/)+3 (at n///sub 2/)+1) n*n grid ((/sup 2/)*(/sup 2/) grid, respectively). d, (2n-6)*(3n-6) larger than /sup 1///sub d-2/ radians 5n-15 bends. These results give in some cases considerable improvements over previous results, bounds other cases. Several e.g. concerning visibility representations, are included. >
sci-hub.se 参考文章(22)
Goos Kant, Hans L. Bodlaender, Planar Graph Augmentation Problems (Extended Abstract). workshop on algorithms and data structures. pp. 286- 298 ,(1991)
Goos Kant, Hans L. Bodlaender, Planar graph augmentation problems workshop on algorithms and data structures. pp. 286- 298 ,(1991) , 10.1007/BFB0028270
Goossen Kant, Triangulating Planar Graphs While Minimizing the Maximum Degree scandinavian workshop on algorithm theory. pp. 258- 271 ,(1992) , 10.1007/3-540-55706-7_22
Norishige Chiba, Takao Nishizeki, Shigenobu Abe, Takao Ozawa, A linear algorithm for embedding planar graphs using PQ-trees Journal of Computer and System Sciences. ,vol. 30, pp. 54- 76 ,(1985) , 10.1016/0022-0000(85)90004-2
J. Nummenmaa, Constructing compact rectiliner planar layouts using canonical representation of planar graphs Theoretical Computer Science. ,vol. 99, pp. 213- 230 ,(1992) , 10.1016/0304-3975(92)90349-K
Seth Malitz, On the angular resolution of planar graphs symposium on the theory of computing. pp. 527- 538 ,(1992) , 10.1145/129712.129764
Roberto Tamassia, Giuseppe Di Battista, Carlo Batini, Automatic graph drawing and readability of diagrams systems man and cybernetics. ,vol. 18, pp. 61- 79 ,(1988) , 10.1109/21.87055
Walter Schnyder, Embedding planar graphs on the grid symposium on discrete algorithms. pp. 138- 148 ,(1990) , 10.5555/320176.320191
J. E. Hopcroft, R. E. Tarjan, Dividing a Graph into Triconnected Components SIAM Journal on Computing. ,vol. 2, pp. 135- 158 ,(1973) , 10.1137/0202012
Roberto Tamassia, On embedding a graph in the grid with the minimum number of bends SIAM Journal on Computing. ,vol. 16, pp. 421- 444 ,(1987) , 10.1137/0216030