| 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 <[email protected]>, [email protected] (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 13: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
| |||||