Title: | Mathematics at DEC |
Moderator: | RUSURE::EDP |
Created: | Mon Feb 03 1986 |
Last Modified: | Fri Jun 06 1997 |
Last Successful Update: | Fri Jun 06 1997 |
Number of topics: | 2083 |
Total number of notes: | 14613 |
In article <183@ucrmath.UUCP>, marek@ucrmath.UUCP (Marek Chrobak) asks: > QUESTION 1: Does there exist a set of n points in the plane > such that every n-vertex planar graph can be drawn in the plane > such that the vertices are mapped onto these points, and edges > are straight line segments? > > Let us call such a set an n-universal set. Frankly, I don't > believe that such sets exist (if n is large enough). It is > easy to see that we can only consider triangulated graphs. I think this problem can be fairly easily solved by some readers of this conference (although I haven't yet solved it). One thing I've realized is that the convex hull of the n-universal set, n >= 3, (assuming such a set exists) contains exactly 3 points.
T.R | Title | User | Personal Name | Date | Lines |
---|---|---|---|---|---|
865.2 | 7 solved | HERON::BUCHANAN | a small Bear travels thro' a Forest | Fri Jun 10 1988 17:04 | 54 |
(New results added) We are interested in determining criteria for a set of n points, S, to be n-universal. In particular, we want to know for which n does an n-universal set exist. In all that follows, we assume that in no S are three points collinear. Define: Say S is a set of n points. If bdry(S), the boundary of the convex hull of S contains exactly m of the points of S, then write: m = B(S) * Nec & suf conditions for S to be n-universal, for n =< 7 ======================================================== n =< 3 Trivial n = 4 or 5 B(S) = 3 n = 6 B(S) = 3 For all points x in S, B(S\{x}) =< 4 n = 7 B(S) = 3 For all points x in S, B(S\{x}) =< 5 * Nec conditions for S to be n-universal, for n >= 8 ================================================== B(S) = 3 For all points x in S, B(S\{x}) =< c1(n), where if n = 8,9,10 or 12 then c1(n) = 5 otherwise c1(n) = 6 For n >= 9: For all pairs of points {x,y} drawn from S, B(S\{x,y}) =< c2(n) where: c2(10) = 7 c2(12) = 6 otherwise c2(n) = 9 For n = 12: B(S\bdry(S)) =< 6 * Andrew Buchanan |