An Algorithm for Placing Edge Labels in a Graph Drawing by Simple Rules

Takurou YAMAJI  Sumio MASUDA  Noboru ABE  Kazuaki YAMAGUCHI  

Publication
A - Abstracts of IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences (Japanese Edition)   Vol.J100-A   No.10   pp.363-373
Publication Date: 2017/10/01
Online ISSN: 1881-0195
Type of Manuscript: PAPER
Category: 
Keyword: 
graph,  drawing,  heuristic algorithm,  labeling,  

Full Text(in Japanese): PDF(875.8KB)
>>Buy this Article


Summary: 
Let G be a graph and let be a drawing of G. In this paper, we consider the problem of placing edge labels in in such a way that labels do not overlap other labels, vertices and edges. The objective of the problem is to place as many labels as possible. For this problem, we propose a new heuristic algorithm based on the map labeling algorithms that use the slider model and several rules. Our method basically determines label locations by three simple rules. Experimental results show that our method is superior than two previous methods with respect to the number of placed labels.