6 results for Archdeacon, Dan

  • Halin's Theorem for Cubic Graphs on an Annulus

    Archdeacon, Dan; Bonnington, C. Paul; Siran, Jozef (2001-06)

    Report
    The University of Auckland Library

    Halin's Theorem characterizes those locally-finite, 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; Ellis-Monaghan, Jo (2004-07)

    Report
    The University of Auckland Library

    Steinitz's Theorem states that a graph is the 1-skeleton of a convex polyhedron if and only if it is 3-connected 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
  • Obstructions for Embedding Cubic Graphs on the Spindle Surface

    Archdeacon, Dan; Bonnington, C. Paul (2001-09)

    Report
    The University of Auckland Library

    The {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 nearly-planar} if there exists an edge $e$ such that $G - e $ is planar. All planar graphs are nearly-planar. A cubic obstruction for near-planarity is the same as an obstruction for embedding on the spindle surface. Hence we also give the topological obstruction set for cubic nearly-planar graphs.

    View record details
  • Trading crossings for handles and crosscaps

    Archdeacon, Dan; Bonnington, C. Paul; Siran, Jozef (2000-11)

    Report
    The University of Auckland Library

    Let $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 trade-off 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 doubly-toroidal graphs. For every $epsilon > 0$ we construct graphs whose orientable crossing sequence satisfies $c_1/c_0 > 5/6-epsilon$. 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 non-orientable crossing sequence} $tilde c_0, tilde c_1, tilde c_2,dots$ for drawings on non-orientable surfaces. We show that for every $tilde c_0 > tilde c_1 > 0$ there exists a graph with non-orientable crossing sequence $tilde c_0, tilde c_1, 0$. We conjecture that every strictly-decreasing sequence of non-negative integers can be both an orientable crossing sequence and a non-orientable crossing sequence (with different graphs).

    View record details
  • Halin's Theorem for the M"obius Strip

    Archdeacon, Dan; Bonnington, C. Paul; Debowsky, Marisa; Prestidge, Michael (2001-08)

    Report
    The University of Auckland Library

    Halin's Theorem characterizes those locally finite 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 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
  • Sewing Ribbons on Graphs in Space

    Archdeacon, Dan; Bonnington, Paul; Richter, Bruce; Siran, Jozef (2000)

    Report
    The University of Auckland Library

    An {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 3-dimensional 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