| Abstract: | The following definition is motivated by the study of circle orders and their connections to graphs. A graphs G is called a point-halfspace graph (in R k) provided one can assign to each vertex v ? (G) a point p v R k and to each edge e ? E(G) a closed halfspace He ? R k so that v is incident with e if and only if p v ? He. Let H k denote the set of point-halfspace graphs (in R k). We give complete forbidden subgraph and structural characterizations of the classes H k for every k. Surprisingly, these classes are closed under taking minors and we give forbidden minor characterizations as well. © 1996 John Wiley & Sons, Inc. |
