تعبیه¬ی هندسی درخت درنقاط داخل یک چندضلعی با حداقل تعداد خم
الموضوعات :
1 - دانشگاه آزاد اسلامی قزوین
2 - دانشگاه صنعتی امیرکبیر
الکلمات المفتاحية: تعبیه¬ی هندسی, تعبیه¬ی درخت در مجموعه نقاط, به حداقل رساندن خم, تطبیق¬دهی گراف,
ملخص المقالة :
دراین مقاله در نظر داریم تا یک درخت با N گره را روی N نقطه داخل یک چند ضلعی با n رأس تعبیه کنیم این تعبیه باید به گونه ای باشد که تعداد خم های درخت حاصل حداقل شود. ایده ی اصلی الگوریتم جدید مدل کردن مسئله به صورت مسئله ی تطبیق دهی گراف ها واستفاده از الگوریتم های تطبیق دهی گراف است که منجر به بررسی مسئله ی فاصله ی پیوندی و مسیر با حداقل تعداد لینک می شود، سپس با به کار بردن مفهوم تصحیح خطا ویافتن یک تابع هزینه ی مناسب و استفاده از روش تجزیه ی گراف ها، تطبیق دهی گراف ها را با حداقل هزینه برای به حداقل رساندن تعداد خم انجام می-دهیم و الگوریتم دارای پیچیدگی محاسباتی 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.