A more compact visibility representation

被引:32
作者
Kant, G [1 ]
机构
[1] UNIV UTRECHT,DEPT COMP SCI,NL-3584 CH UTRECHT,NETHERLANDS
关键词
graph drawing; visibility; compact; 4-block tree;
D O I
10.1142/S0218195997000132
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
In this paper we present a linear time and space algorithm for constructing a visibility representation of a planar graph on an (right perpindicular 3/2n left perpendicular - 3) x (n - 1) grid, thereby improving the previous bound of (2n - 5) x (n - 1). To this end we build in linear time the 4-blode tree of a planar graph, which improves previous time bounds. Moreover, this is the first time that the technique of splitting a graph into its 4-connected components is used successfully in graph drawing.
引用
收藏
页码:197 / 210
页数:14
相关论文
共 23 条
  • [1] BERTOLAZZI P, 1992, LECT NOTES COMPUT SC, V621, P272
  • [2] Biedl T.C., 1994, LECT NOTES COMP SCI, V824, P83
  • [3] ARBORICITY AND SUBGRAPH LISTING ALGORITHMS
    CHIBA, N
    NISHIZEKI, T
    [J]. SIAM JOURNAL ON COMPUTING, 1985, 14 (01) : 210 - 223
  • [4] CONSTRAINED VISIBILITY REPRESENTATIONS OF GRAPHS
    DIBATTISTA, G
    TAMASSIA, R
    TOLLIS, IG
    [J]. INFORMATION PROCESSING LETTERS, 1992, 41 (01) : 1 - 7
  • [5] DIBATTISTA G, 1992, DISCRETE COMPUT GEOM, V7, P381, DOI 10.1007/BF02187850
  • [6] ALGORITHMS FOR DRAWING GRAPHS - AN ANNOTATED-BIBLIOGRAPHY
    DIBATTISTA, G
    EADES, P
    TAMASSIA, R
    TOLLIS, IG
    [J]. COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 1994, 4 (05): : 235 - 282
  • [7] DIBATTISTA G, 1995, IN PRESS 11 ANN ACM
  • [8] EPPSTEIN D, 1995, PROCEEDINGS OF THE SIXTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P632
  • [9] Garg A., 1994, LECT NOTES COMPUTER, V855, P12, DOI [10.1007/BFb0049393, DOI 10.1007/BFB0049393]
  • [10] HE X, 1995, TR9506 STAT U NEW YO