ON POINT-HALF-SPACE GRAPHS

The following definition is motivated by the study of circle orders an d their connections to graphs. A graph G is called a point-halfspace g raph (in R(k)) provided one can assign to each vertex upsilon is an el ement of V(G) a point p(upsilon) is an element of R(k) and to each edg e e is an element of E(G) a closed halfspace H-e subset of R(k) so tha t upsilon is incident with e if and only if p(upsilon) is an element o f H-e. Let H-k denote the set of point-halfspace graphs (in R(k)). We give complete forbidden subgraph and structural characterizations of t he classes H-k for every k. Surprisingly, these classes are closed und er taking minors and we give forbidden minor characterizations as well . (C) 1995 John Wiley & Sons, Inc.