ContactPerson: xinhe@cse.buffalo.edu
Remote host: deneb.cse.buffalo.edu
Remote ident: xinhe
### Begin Citation ### Do not delete this line ###
%R 2000-08
%U /u0/csestaff/stock/box.ps
%A Xin He
%T A Simple Linear Time Algorithm for Proper Box Rectangular Drawing of Plane Graphs
%D August 10, 2000
%I Department of Computer Science and Engineering, SUNY Buffalo
%K Graph Drawing, Algorithms
%X In this paper we introduce a new drawing style of a plane graph 
G, called "proper box rectangular" (PBR) drawing. It is defined 
to be a drawing of G such that every vertex is drawn as a 
rectangle, called a box, each edge is drawn as either a horizontal 
or a vertical line segment, and each face is drawn as a rectangle. 
We establish necessary and sufficient conditions for G 
to have a PBR drawing. We also give a simple linear time algorithm 
for finding such drawings. The PBR drawing is closely related to the 
"box rectangular" (BR) drawing defined by Rahman, Nakano and 
Nishizeki. Our method can be adapted to provide a new 
simpler algorithm for solving the BR drawing problem.