Mathematics and Statistics Vol. 1(3), pp. 135 - 143
DOI: 10.13189/ms.2013.010305
Reprint (PDF) (139Kb)

On r-Edge-Connected r-Regular Bricks and Braces and Inscribability

Kevin K. H. Cheung^*
School of Mathematics and Statistics Carleton University 1125 Colonel by Drive Ottawa, ON K1S 5B6 Canada

ABSTRACT

A classical result due to Steinitz states that a graph is isomorphic to the graph of some 3-dimensional polytope P if and only if it is planar and 3-connected. If a graph G is isomorphic to the graph of a 3-dimensional polytope inscribed in a sphere, it is said to be of inscribable type. The problem of determining which graphs are of inscribable type dates back to 1832 and was open until Rivin proved a characterization in terms of the existence of a strictly feasible solution to a system of linear equations and inequalities which we call sys(G), which, surprisingly, also appears in the context of the Traveling Salesman Problem. Using such a characterization, various classes of graphs of inscribable type can be described. Dillencourt and Smith gave a characterization of 3-connected 3-regular planar graphs that are of inscribable and a linear-time algorithm for recognizing such graphs. In this paper, their results are generalized to r-edge-connected r-regular graphs for odd r ≥ 3 in the context of the existence of strictly feasible solutions to sys(G). An answer to an open question raised by D. Eppstein concerning the inscribability of 4-regular graphs is also given.

KEYWORDS
Inscribable, Polytope, Regular, Graph, Sphere

Cite This Paper in IEEE or APA Citation Styles
(a). IEEE Format:
[1] Kevin K. H. Cheung , "On r-Edge-Connected r-Regular Bricks and Braces and Inscribability," Mathematics and Statistics, Vol. 1, No. 3, pp. 135 - 143, 2013. DOI: 10.13189/ms.2013.010305.

(b). APA Format:
Kevin K. H. Cheung (2013). On r-Edge-Connected r-Regular Bricks and Braces and Inscribability. Mathematics and Statistics, 1(3), 135 - 143. DOI: 10.13189/ms.2013.010305.