MathDB
Embed a graph on given points

Source: KöMaL A. 731

November 12, 2018
combinatorics

Problem Statement

Let G=(V,E)G=(V,E) be a tree graph with nn vertices, and let PP be a set of nn points in the plane with no three points collinear. Is it true that for any choice of graph GG and set PP, we can embed GG in PP, i.e., we can find a bijection f:V→Pf:V\to P such that when we draw line segment [f(x),f(y)][f(x),f(y)] for all (x,y)∈E(x,y)\in E, no two such segments intersect each other?
Back to ProblemsView on AoPS