General Profile


David Barnette

Professor Emeritus
Graph theory
Ph.D., 1967, University of Washington

Office: 0

AMS Math Reviews

Professor David W. Barnette studies graph theory and combinatorial geometry. He has considered various questions about such geometric objects as convex polytopes and triangulations of manifolds. Some of these questions have implications in topology, in particular for invariants such as Gromov norm and decision problems for triangulated manifolds.

One of Professor Barnette's results with a concise statement concerns the number of k-dimensional faces of an n-dimensional polytope [1, 2]. He proved that if such a polytope is simplicial and has v vertices, then it has at least (d choose k)v - (d+1 choose k+3)(d-1-k) k-dimensional faces. This result and others convey the general theme that high-dimensional convex polytopes are necessarily very complicated.

Professor Barnette has also studied the problem of finding minimal triangulations of surfaces. Here a triangulation must be the "honest" kind in which two triangles cannot share two vertices without also sharing an edge connecting them. A triangulation is minimal if there is no way to contract an edge to a point to obtain a simpler triangulation. He proved that the projective plane has only two minimal triangulations [3], and later he and Edelson [4] proved that any closed surface has finitely many minimal triangulations. These results allow for new kinds of arguments by induction on triangulations of surfaces. They are also similar in spirit to Kuratowski's classical theorem that a graph is non-planar if and only if it has five vertices connected by disjoint paths or three vertices connected to three others by disjoint paths.

Selected publications

  1. The minimum number of vertices of a simple polytope, Israel J. Math. 10 (1971), 121-125.

  2. A proof of the lower bound theorem for convex polytopes, Pacific J. Math. 46 (1973), 349-354.

  3. Generating the triangulations of the projective plane, J. Combin. Theory Ser. B 39 (1982), 222-230.

  4. All 2-manifolds have finitely many minimal triangulations, Israel J. Math. 67 (1989), 123-128.

  5. A construction of 3-connected graphs, Israel J. Math. 86 (1994), 397-407.

Last updated: 0000-00-00