A note on graphs and sphere orders

A partially ordered set P is called a k-sphere order if one can assign to each element a ∈ P a ball B_a in R^k so that a < b iff B_a ? B_b. To a graph G = (V,E) associate a poset P(G) whose elements are the vertices and edges of G. We have v < e in P(G) exactly when v ∈ V, e ∈ E, and v is an end point of e. We show that P(G) is a 3-sphere order for any graph G. It follows from E. R. Scheinerman [“A Note on Planar Graphs and Circle Orders,” SIAM Journal of Discrete Mathematics, Vol. 4 (1991), pp. 448–451] that the least k for which G embeds in R^k equals the least k for which P(G) is a k-sphere order. For a simplicial complex K one can define P(K) by analogy to P(G) (namely, the face containment order). We prove that for each 2-dimensional simplicial complex K, there exists a k so that P(K) is a k-sphere order. © 1993 John Wiley & Sons, Inc.