NON-CROSSING CONFIGURATIONS IN COMPLEMENTS OF GEOMETRIC GRAPHS AND DISJOINT COMPATIBILITY
Abstract
In this article, for any non-crossing perfect matching a disjoint compatible spanning tree with a maximum vertex degree no more than 4 is constructed with the complexity O(n4 log n) The criterion of existence of a non-crossing perfect matching in the complement of a star of the order less than 2n in K2n has been obtained. It has been proved that there exists a noncrossing perfect matching in the complement of a tree of the order (n + 1) in K2n with the number of inner vertices no more than (n – 1).
About the Author
V. I. BENEDIKTOVICH
Institute of Mathematics of the National Academy of Sciences of Belarus
Belarus
Belarus
References
1. Ishaque, M. Disjoint compatible geometric matchings / M. Ishaque, D. L. Souvaine, C. D. Tóth // Proceedingsof the 27th Symposium on Computational Geometry (Paris, 2011). – New York, 2011. – P. 125–134.
2. Bose, P. Growing a tree from its branches / P. Bose, G. T. Toussaint, // J. Algorithm. – 1995. – Vol. 19, N 1. – P. 86–103.
3. Bose, P. Every set of disjoint segments admits a binary tree / P. Bose, M. E. Houle, G. T. Toussaint // Discr. Comput. Geom. – 2001. – Vol. 26, N 3. – P. 387–410.
4. Hoffmann, M. Pointed binary encompassing trees: simple and optimal / M. Hoffmann, C. D. Toth // Comput. Geom. Theor. Appl. – 2010. – Vol. 43, N 1. – P. 35–41.
5. Souvaine, D. L. A vertex- face assignment for plane graphs / D. L. Souvaine, C. D. Tóth, // Comp. Geom. Theor. Appl. – 2009. – Vol. 42, N 5. – P. 388–394.
6. Rappaport, D. Computing simple circuits from a set of line segments is NP-complete / D. Rappaport // SIAM J. Comput. – 1989. – Vol. 18, N 6. – P. 1128–1139.
7. Compatible geometric matchings / O. Aichholzer [et al.] // Comp. Geom. Theor. Appl. – 2009. – Vol. 42. – P. 617–626.
8. Convex partitions with 2-edge connected dual graphs / M. Al-Jubeh [et al.] // J. Combin. Opt. – 2011. – Vol. 22, N 3. – P. 409–425.
9. Edge-removal and non-crossing configurations in geometric graphs / O. Aichholzer [et al.] // Discr. Math. Theor. Comput. Sci. – 2010. – Vol. 12, N 1. – P. 75–86.
Review
Views: 700
Email this article 