A relational graph structure based on a boundary representation of solid objects is described. In this structure, called face adjacency graph, nodes represent object faces, whereas edges and vertices are encoded into arcs and hyperarcs. Based on the face adjacency graph, we define a set of primitive face-oriented Euler operators, and a set of macrooperators for face manipulation, which allow a compact definition and an efficient updating of solid objects. We briefly describe a hierarchical graph structure based on the face adjacency graph, which provides a representation of an object at different levels of detail. Thus it is consistent with the stepwise refinement process through which the object description is produced.