同步邊界標籤之演算法設計與分析

Algorithm Design and Analysis for Simultaneous Boundary Labeling

鍾家涵(Chia-Han Chung)

指導教授 ： 顏嗣鈞

國立臺灣大學/電機資訊學院/電機工程學研究所/碩士(2016年)

https://doi.org/10.6342/NTU201600238

摘要

無資料

關鍵字

simultaneous graph drawing ； boundary labeling ； crossing minimization ； bipartite matching ； barycenter algorithm

並列摘要

In boundary labeling, each feature point is connected to a label placed
on the boundary of a rectangular image by a leader, which may be a rectilinear
or a straight line segment. Currently, all the research about boundary
labeling focuses on how to generate label placements for one image with high
readability. However, there may be a series of related images, which share
all, or parts of the same feature and label set, need to be labeled. If we calculate
label placements for each image separately, it is hard to keep track of
the relationship between images. To overcome the above difficulty, in this
thesis we propose a new problem called simultaneous boundary labeling. We
keep the relationship between images by limiting common features and labels
of a series of images in the same place, and find a common label placement
for all images with minimal leader crossing number and minimal total leader
length to increase the readability. We design some heuristic algorithms when
there are two related images need to be labeled and show the problem to be
NP-complete when there are more than four images in the series. The leader
length minimization problem can be solved by a weighted bipartite matching
algorithm.

並列關鍵字

simultaneous graph drawing ； boundary labeling ； crossing minimization ； bipartite matching ； barycenter algorithm

參考文獻

[1] On simultaneous planar graph embeddings. Computational Geometry, 36(2):117 – 130, 2007.

[2] M. A. Bekos, M. Kaufmann, M. Nollenburg, and A. Symvonis. Boundary labeling with octilinear leaders. Algorithmica, 57(3):436–461, 2009.

[3] M.A.Bekos,M.Kaufmann,A.Symvonis,andA.Wolff.Boundarylabeling:Models and efficient algorithms for rectangular maps. Computational Geometry, 36(3):215 – 236, 2007.

[7] C. Demetrescu and I. Finocchi. Breaking cycles for minimizing crossings. Journal of Experimental Algorithmics, 6, 2001.

ter Simultaneous Graph Drawing: Layout Algorithms and Visualization Schemes, pages 437–449. Springer Berlin Heidelberg, Berlin, Heidelberg, 2004.