Improved visibility representation of plane graphs

In a visibility representation (VR for short) of a plane graph G, each vertex of G is represented by a horizontal line segment such that the line segments representing any two adjacent vertices of G are joined by a vertical line segment. Rosenstiehl and Tarjan [Discrete Comput. Geom. 1 (1986) 343-353] and Tamassia and Tollis [Discrete Comput. Geom. 1 (1986) 321-341] independently gave linear time VR algorithms for 2-connected plane graph. Using this approach, the height of the VR is bounded by (n-1), the width is bounded by (2n-5). After that, some work has been done to find a more compact VR. Kant and He [Theoret. Comput. Sci. 172 (1997) 175-193] proved that a 4-connected plane graph has a VR with width bounded by (n-1). Kant [Internat. J. Comput. Geom. Appl. 7 (1997) 197-210] reduced the width bound to ⌊3n-62⌋ for general plane graphs. Recently, using a sophisticated greedy algorithm, Lin et al. reduced the width bound to ⌊22n-4215⌋ [Proc. STACS'03, Lecture Notes in Computer Science, vol. 2607, Springer, Berlin, 2003, pp. 14-25]. In this paper, we prove that any plane graph G has a VR with width at most ⌊13n- 249⌋, which can be constructed by using the simple standard VR algorithm in [P. Rosenstiehl, R.E. Tarjan, Discrete Comput. Geom. 1 (1986) 343-353; R. Tamassia, I.G. Tollis, Discrete Comput. Geom. 1 (1986) 321-341].