کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10118366 | 1632853 | 2005 | 37 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
2-restricted extensions of partial embeddings of graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Let K be a subgraph of G. Suppose that we have a 2-cell embedding of K in some surface and that for each K-bridge in G, one or two simple embeddings in faces of K are prescribed. Obstructions for existence of extensions of the embedding of K to an embedding of G are studied. It is shown that minimal obstructions possess certain combinatorial structure that can be described in an algebraic way by means of forcing chains of K-bridges. The geometric structure of minimal obstructions is also described. It is shown that they have “millipede” structure that was observed earlier in some special cases (disc, Möbius band). As a consequence it is proved that if one is allowed to reroute the branches of K, one can obtain a subgraph Kâ² of G homeomorphic to K for which an obstruction of bounded branch size exists. The precise combinatorial and geometric structure of corresponding obstructions can be used to get a linear time algorithm for either finding an embedding extension or discovering minimal obstructions.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 26, Issues 3â4, AprilâMay 2005, Pages 339-375
Journal: European Journal of Combinatorics - Volume 26, Issues 3â4, AprilâMay 2005, Pages 339-375
نویسندگان
Martin Juvan, Bojan Mohar,