An Algorithm for Labeling Edges of Hierarchical Drawings

Konstantinos G. Kakoulis and Ioannis G. Tollis

Department of Computer Science
The University of Texas at Dallas
Richardson, TX 75083-0688
kostant@utdallas.edu, tollis@utdallas.edu

Abstract

Let G(V,E) be a graph, and let Gamma be the drawing of G on the plane. We consider the problem of assigning text labels to every edge of G such that the quality of the labeling assignment is optimal. This problem has been rst encountered in automated cartography. Even though much effort has been devoted over the last 15 years in the area of automated drawing of maps, the Edge Label Placement (ELP) problem remains essentially unsolved. In this paper we investigate the ELP problem. We present an algorithm for the ELP problem more suitable for hierarchical drawings of graphs, but it can be adopted to many di erent drawing styles and still remain effective. Also, we present experimental results of our algorithm that indicate its effectiveness.

The full paper is available.