Subtour elimination polytopes and graphs of inscribable type

The subtour-elimination polytope (SEP) of a graph G is the feasible region of the linear programming relaxation of an important integer linear programming formulation of the Symmetric Travelling Salesman Problem (STSP) on G.; The SEP is a well-studied combinatorial object at least in the case of the complete graph and is often used as a starting point for solving concrete STSPs. Remarkably, the SEP is related to the century-old geometry problem of determining if a 3-connected planar graph is of inscribable type, that is, realizable by a 3-dimensional polytope inscribed in the sphere. The problem was open for over a century until Rivin showed that G is of inscribable type if and only if there exists a point in the SEP of G that satisfies all the inequalities strictly.; In this thesis, we study the SEP of a general simple graph and graphs of inscribable type. In particular, questions on the existence of certain points in the SEP and the certificates of unsolvability of the system that defines the polytope are considered. Some graph operations that preserve the property that the system has a solution that satisfies all the inequalities strictly are also described. The SEP of a (2k + 1)-edge-connected (2k + 1)-regular graph is studied in detail. In particular, an efficient algorithm for computing the dimension of the SEP of such a graph is given. A detailed sketch of Rivin's elementary proof of his theorem is given in the context of the SEP. Descriptions of classes graphs of inscribable type are obtained in the thesis.