6 results for Archdeacon, Dan

Halin's Theorem for Cubic Graphs on an Annulus
Archdeacon, Dan; Bonnington, C. Paul; Siran, Jozef (200106)
Report
The University of Auckland LibraryHalin's Theorem characterizes those locallyfinite, infinite graphs that embed in the plane without accumulation points by giving a set of six topologically excluded subgraphs. We prove the analogous theorem for cubic graphs that embed in an annulus without accumulation points, finding the complete set of 29 excluded subgraphs.
View record details 
How to Exhibit Toroidal Maps in Space
Archdeacon, Dan; Bonnington, C. Paul; EllisMonaghan, Jo (200407)
Report
The University of Auckland LibrarySteinitz's Theorem states that a graph is the 1skeleton of a convex polyhedron if and only if it is 3connected and planar. The polyhedron is called a geometric realization of the embedded graph. Its faces are bounded by convex polygons whose points are coplanar. A map on the torus does not necessarily have such a geometric realization. In this paper, we relax the condition that faces are the convex hull of coplanar points. We require instead that the convex hull of the p oints on a face can be projected onto a plane so that the boundary of the convex hull of the projected points is the image of the boundary of the face. We also require that the interiors of the convex hulls of different faces do not intersect. Call this an exhibition of the map. A map is polyhedral if the intersection of any two closed faces is simply connected. Our main result is that every polyhedral toroidal map can be exhibited. As a corollary, every toroidal triangulation has a geometric realization.
View record details 
Halin's Theorem for the M"obius Strip
Archdeacon, Dan; Bonnington, C. Paul; Debowsky, Marisa; Prestidge, Michael (200108)
Report
The University of Auckland LibraryHalin's Theorem characterizes those locally finite infinite graphs that embed in the plane without accumulation points by giving a set of six topologicallyexcluded subgraphs. We prove the analogous theorem for graphs that embed in an open M"obius strip without accumulation points. There are 153 such obstructions under the ray ordering defined herein. There are 350 obstructions under the minor ordering. There are 1225 obstructions under the topological ordering. The relationship between these graphs and the obstructions to embedding in the projective plane is similar to the relationship between Halin's graphs and ${ K_5 , K_{3,3} }$.
View record details 
Obstructions for Embedding Cubic Graphs on the Spindle Surface
Archdeacon, Dan; Bonnington, C. Paul (200109)
Report
The University of Auckland LibraryThe {em spindle surface} $S$ is the pinched surface formed by identifying two points on the sphere. In this paper we examine cubic graphs that minimally do not embed on the spindle surface. We give the complete list of 21 cubic graphs that form the topological obstruction set in the cubic order for graphs that embed on $S$. A graph $G$ is {em nearlyplanar} if there exists an edge $e$ such that $G  e $ is planar. All planar graphs are nearlyplanar. A cubic obstruction for nearplanarity is the same as an obstruction for embedding on the spindle surface. Hence we also give the topological obstruction set for cubic nearlyplanar graphs.
View record details 
Trading crossings for handles and crosscaps
Archdeacon, Dan; Bonnington, C. Paul; Siran, Jozef (200011)
Report
The University of Auckland LibraryLet $c_k = cr_k(G)$ denote the minimum number of edge crossings when a graph $G$ is drawn on an orientable surface of genus $k$. The (orientable) {em crossing sequence} $c_0,c_1,c_2,dots$ encodes the tradeoff between adding handles and decreasing crossings. We focus on sequences of the type $c_0 > c_1 > c_2 = 0$; equivalently, we study the planar and toroidal crossing number of doublytoroidal graphs. For every $epsilon > 0$ we construct graphs whose orientable crossing sequence satisfies $c_1/c_0 > 5/6epsilon$. In other words, we construct graphs where the addition of one handle can save roughly 1/6th of the crossings, but the addition of a second handle can save 5 times more crossings. We similarly define the {em nonorientable crossing sequence} $tilde c_0, tilde c_1, tilde c_2,dots$ for drawings on nonorientable surfaces. We show that for every $tilde c_0 > tilde c_1 > 0$ there exists a graph with nonorientable crossing sequence $tilde c_0, tilde c_1, 0$. We conjecture that every strictlydecreasing sequence of nonnegative integers can be both an orientable crossing sequence and a nonorientable crossing sequence (with different graphs).
View record details 
Sewing Ribbons on Graphs in Space
Archdeacon, Dan; Bonnington, Paul; Richter, Bruce; Siran, Jozef (2000)
Report
The University of Auckland LibraryAn {em open ribbon} is a square with one side called the {em seam}. A {em closed ribbon} is a cylinder with one boundary component called the {em seam}. We {em sew} an open (resp.~closed) ribbon onto a graph by identifying the seam with an open (resp.~closed) walk in the graph. A {em ribbon complex} is a graph with a finite number of ribbons sewn on. We investigate when a ribbon complex embeds in 3dimensional Euclidean space. We give several characterizations of such {em spatial} complexes which lead to algorithms. We examine special cases where: 1) each edge of the graph is incident with at most three ribbons, and 2) every ribbon is closed together with a connectivity condition.
View record details