تعبیه¬ی هندسی درخت درنقاط داخل یک چندضلعی با حداقل تعداد خم
محورهای موضوعی :
اکرم سپهری
1
(دانشگاه آزاد اسلامی قزوین)
علیرضا باقری
2
(دانشگاه صنعتی امیرکبیر)
کلید واژه: تعبیه¬ی هندسی, تعبیه¬ی درخت در مجموعه نقاط, به حداقل رساندن خم, تطبیق¬دهی گراف,
چکیده مقاله :
دراین مقاله در نظر داریم تا یک درخت با N گره را روی N نقطه داخل یک چند ضلعی با n رأس تعبیه کنیم این تعبیه باید به گونه ای باشد که تعداد خم های درخت حاصل حداقل شود. ایده ی اصلی الگوریتم جدید مدل کردن مسئله به صورت مسئله ی تطبیق دهی گراف ها واستفاده از الگوریتم های تطبیق دهی گراف است که منجر به بررسی مسئله ی فاصله ی پیوندی و مسیر با حداقل تعداد لینک می شود، سپس با به کار بردن مفهوم تصحیح خطا ویافتن یک تابع هزینه ی مناسب و استفاده از روش تجزیه ی گراف ها، تطبیق دهی گراف ها را با حداقل هزینه برای به حداقل رساندن تعداد خم انجام می-دهیم و الگوریتم دارای پیچیدگی محاسباتی O(N2n+N4)است.
In this article, we intend to embed a tree with N nodes on N points inside a polygon with n vertices. This embedding should be in such a way that the number of bends in the resulting tree is minimized. The main idea of the new algorithm is to model the problem as a graph matching problem and use algorithms It is graph matching that leads to the examination of the link distance problem and the path with the minimum number of links, then by using the concept of error correction and finding a suitable cost function and using the graph analysis method, graph matching is done. We do it with minimal cost to minimize the number of bends and the algorithm has a computational complexity of O(N2n+N4).
[1] Abellanas M, Garcia-Lopez J, Hernnandez G, Noy M, P. Ramos A. Bipartite embeddings of trees in the plane. Discrete Applied Mathematics, pp: 1-10,1999.
[2] Badent M, Giacomo E.D, Liotta G. Drawing colored graphs on colored points, in Proceedings of the Tenth Workshop on Algorithms and Data Structures, pp: 129-142,2008.
[3] Bagheri A.R, Razzazi M.R. On complexity of planar embeddability of trees inside simple polygons. Information processing letters,
pp: 521-523,2010.
[4] Bose P. On embedding an outer-planar graph on a point set,computational Geometry: Theory and Applications, pp: 303–312,2002.
[5] Bose P, McAllister M, Snoeyink J. Optimal algorithms to embed trees in a point set, Journal of Graph Algorithms and Applications, pp: 1–15, 1997.
[6] Binucci C , Di Giacomo E , Didimo W , Estrella-Balderrama A, Frati F, GKobourov S, Liotta G. Upward straight-line embeddings of directed graphs into point sets, Computational Geometry, pp: 219–232, 2010.
[7] Cabello S. Planar embeddability of the vertices of a graph using a fixed point set is NP-hard, J. Graph Algorithms Appl, pp:353–366,2006.
[8] Giacomo E.D, Didimo W, Liotta G, Meijer H, Wismath S.k. Point-set embeddings of trees with given partial drawings, Computational Geometry, pp: 664-676, 2009.
[9] Giacomo E. D, Liotta G, Trotta F. On embedding a graph on two sets of points, International Journal of Foundations of Computer Science, pp: 1071–1094, 2006.
[10] El-sonbaty Y, ismail M. A. A new algorithm for subgraph optimal Isomorphism, Pattern Recognition Society, published by Elsevier Science, pp: 205-218, 1997.
[11] Gritzmann P, Mohar B, Pach J, Pollack R. Embedding a planar triangulation with vertices at specified positions. The American Mathematical Monthly 98, pp: 165–166, 1991.
[12] Kaufmann M, Wiese R. Embedding vertices at points: Few bends suffice for planar graphs, Journal of Graph Algorithms and Applications, pp: 115–129, 2002.
[13] Pach J, Wenger R. Embedding planar graphs at fixed vertex locations, Graphs and Combinatory, pp: 717–728, 2001.
[14] Suri S. A linear time algorithm for minimum link paths inside a simple polygon, Computer Vision Graphics and Image Process, pp: 99-110, 1986.
[15] Yamada S, Hasai T. An efficient algorithm for the linear assignment problem, Elect. Comm, pp: 28-36, 1990.