Bipartite embeddings of trees in the plane

التفاصيل البيبلوغرافية
العنوان: Bipartite embeddings of trees in the plane
المؤلفون: G. Hernández, M. Abellanas, Marc Noy, Jesús García, Pedro Ramos
المصدر: Scopus-Elsevier
بيانات النشر: Elsevier Science B.V.
مصطلحات موضوعية: Combinatorics, Convex hull, Embedding problem, Discrete mathematics, Applied Mathematics, Bipartite graph, Embedding, Discrete Mathematics and Combinatorics, Join (topology), Tree (set theory), Disjoint sets, General position, Mathematics
الوصف: Given a tree T on n vertices and a set P of n points in the plane in general position, it is known that T can be straight line embedded in P without crossings. Now imagine the set P is partitioned into two disjoint subsets R and B, and we ask for an embedding of T in P without crossings and with the property that all edges join a point in R (red) and a point in B (blue). In this case we say that T admits a bipartite embedding with respect to the bipartition (R, B). Examples show that the problem in its full generality is not solvable. In view of this fact we consider several embedding problems and study for which bipartitions they can be solved. We present several results that are valid for any bipartition (R, B) in general position, and some other results that hold for particular configurations of points.
اللغة: English
تدمد: 0166-218X
DOI: 10.1016/S0166-218X(99)00042-6
URL الوصول: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::216b1df5f83dc7cff779eda1c33642a2
حقوق: OPEN
رقم الأكسشن: edsair.doi.dedup.....216b1df5f83dc7cff779eda1c33642a2
قاعدة البيانات: OpenAIRE
الوصف
تدمد:0166218X
DOI:10.1016/S0166-218X(99)00042-6