REGULAR EDGE LABELING OF 4-CONNECTED PLANE GRAPHS AND ITS APPLICATIONS IN GRAPH DRAWING PROBLEMS

In this paper we extend the concept of the regular edge labeling for g eneral plane graphs and for triconnected triangulated plane graphs to 4-connected triangulated plane graphs. We present two different linear time algorithms for constructing such a labeling. By using regular ed ge labeling, we present a new linear time algorithm for constructing r ectangular dual of planar graphs. Our algorithm is simpler than previo usly known algorithms. The coordinates of the rectangular dual constru cted by our algorithm are integers, while the one constructed by known algorithms are real numbers. Our second regular edge labeling algorit hm is based on canonical ordering of 4-connected triangulated plane gr aphs. By using this technique, we present a new algorithm for construc ting visibility representation of 4-connected planar graphs. Our algor ithm reduces the size of the representation by a factor of 2 for such graphs.