[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

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

865.0. "n-universal sets for planar graphs" by CLT::GILBERT () Thu Apr 21 1988 17:16

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.RTitleUserPersonal
Name
DateLines
865.27 solvedHERON::BUCHANANa small Bear travels thro' a ForestFri Jun 10 1988 17:0454
(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