Label Size Maximization for Rectangular Node Labels

• TORIUMI Shigeki

  Information and System Engineering Course, Graduate School of Science and Engineering, Chuo University

• ENDO Hisao

  Hitachi System & Services, Ltd.

• IMAI Keiko

  Department of Information and System Engineering, Faculty of Science and Engineering, Chuo University

Abstract

The label placement problem is one of the most important problems in geographic information systems, cartography, graph drawing, and graphical interface design. In this paper, we considered the label size maximization problem for points with axes-parallel rectangular labels that correspond to character strings and have different widths based on the number of characters. We propose an algorithm for computing the optimum size for the label size maximization problem in the 2-position model and a polynomial time algorithm for the problem in the 4-position model. Our algorithm cannot obtain the maximum value in the 4-position model because the label size maximization problem in the 4-position model is NP-hard. However, our algorithm is efficient in practice, as shown by computational experiments. Further, computational results for JR trains, subways and major private railroads in Tokyo are presented.

Journal

• IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, A

  IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, A 89 (4), 1035-1041, 2006-04-01

  The Institute of Electronics, Information and Communication Engineers

Keywords

• label placement problem
• node label placement
• label size maximization
• rectangular label

Details

• CRID: 1571417127558505216
• NII Article ID: 110007502806
• NII Book ID: AA10826239
• ISSN: 09168508
• Text Lang: en
• Data Source:
  • CiNii Articles