ContactPerson: huazhang@cse.buffalo.edu Remote host: sol.cse.buffalo.edu ### Begin Citation ### Do not delete this line ### %R 2003-10 %U /home/mthgrad/huazhang/vr.pdf %A Zhang, Huaming %A He, Xin %T Improved Visibility Representation of Plane Graphs %D August 27, 2003 %I Department of Computer Science and Engineering, SUNY Buffalo %K Graph; Visibility Representation %X 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 \cite{RT86}, Tamassia and Tollis \cite{TT86} 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 have been done to find a more compact VR. Kant and He \cite{KH97} proved that a 4-connected plane graph has a VR with width bounded by $(n-1)$. Kant \cite{Kant97} reduced the width bound to $\lfloor \frac{3n-6}{2} \rfloor$ for general plane graphs. Recently, using a sophisticated greedy algorithm, Lin et. al. reduced the width bound to $\lfloor \frac {22n-42} {15} \rfloor$ \cite{LLS03}. In this paper, we prove that any plane graph $G$ has a VR with width at most $\lfloor \frac {13n-24}{9} \rfloor$, which can be constructed by using the simple standard VR algorithm in \cite{RT86,TT86}.