On point‐halfspace graphs

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 H e ϵ R k so that v is incident with e if and only if p v ϵ H e . 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.