Abstract | ||
---|---|---|
In this paper we present a linear time and space algorithm for constructing a visibility representation of a planar graph on an (3/2n–3)×(n–1) grid, thereby improving the previous bound of (2n–5)×(n–1). To this end we build in linear time the 4-block tree of a triangulated planar graph. |
Year | DOI | Venue |
---|---|---|
1997 | 10.1007/3-540-57899-4_70 | International Journal of Computational Geometry and Applications |
Keywords | DocType | Volume |
compact visibility representation,linear time,planar graph | Journal | 7 |
Issue | ISBN | Citations |
3 | 3-540-57899-4 | 18 |
PageRank | References | Authors |
1.86 | 12 | 1 |