کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9513474 | 1632464 | 2005 | 27 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Efficient enumeration of sensed planar maps
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We use Liskovets' quotient maps and Robinson's cycle index sums to count 1-, 2- and 3-connected planar maps by number of vertices and edges up to sense-preserving homeomorphism of the embedding sphere. Although Wormald has already counted these maps up to all homeomorphism, sense-reversing as well as sense-preserving, our methods are computationally more efficient for counting these maps up to orientation-preserving homeomorphism and yield closed-form enumeration formulas in the case of 1- and 2-connected maps. Our formula for 1-connected planar maps uses the number of rooted planar maps with i+1 vertices and j+1 faces; we evaluate these numbers using a method that is more efficient than substituting into Tutte's parametric equations, and we also count rooted toroidal maps by number of vertices and faces more efficiently than by substituting into Arquès' explicit formula.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 293, Issues 1â3, 6 April 2005, Pages 263-289
Journal: Discrete Mathematics - Volume 293, Issues 1â3, 6 April 2005, Pages 263-289
نویسندگان
Timothy R. Walsh,