Recent advances in the computer graphics of woven images in 3-space motivate the development of a model for weavings on arbitrary surfaces of higher genus. Our paradigm differs markedly from what Grünbaum and Shepard have provided for the plane. In particular, we induce our weavings from graph imbeddings on surfaces in 3-space. Additionally, we show that the two most frequently invoked subdivision algorithms in computer graphics, the Catmull--Clark and Doo--Sabin algorithms, correspond nicely to topological surgery operations on the induced weavings. The inherently topological formulation of our model permits a graphic designer to superimpose strand colors and geometric attributes---distances, angles, and curvatures---that conform to manufacturing or artistic criteria.

We formulate conditions on a set of log-concave sequences, under which any linear combination of those sequences is log-concave, and further, of conditions under which linear combinations of log-concave sequences that have been transformed by convolution are log-concave. These conditions involve relations on sequences called synchronicity and ratio-dominance, and a characterization of some bivariate sequences as lexicographic. We are motivated by the 25-year-old conjecture that the genus distribution of every graph is log-concave. Although calculating genus distributions is NP-hard, they have been calculated explicitly for many graphs of tractable size, and the three conditions have been observed to occur in the partitioned genus distributions of all such graphs. They are used here to prove the log-concavity of the genus distributions of graphs constructed by iterative amalgamation of double-rooted graph fragments whose genus distributions adhere to these conditions, even though it is known that the genus polynomials of some such graphs have imaginary roots. A blend of topological and combinatorial arguments demonstrates that log-concavity is preserved through the iterations.

This paper introduces paper-strip sculptures, a physical mesh data-structure used to represent 2-manifold mesh surfaces for understanding topological and geometrical aspects of shape modeling with visual and tactual examples. With paper strips it is possible to construct simple paper sculptures that can convincingly illustrate a variety of ideas in shape modeling - such as 2-manifold mesh surfaces, discrete Gaussian curvature, and the Gauss-Bonnet theorem - with hands-on experiments. Such sculptures can also represent links, knots and weaving. Paper-strip sculptures are also useful to represent and understand non-orientable surfaces such as the projective plane and the Klein bottle.

It has recently been shown that if we twist an arbitrary subset of edges of a mesh on an orientable surface, the resulting extended graph rotation system (EGRS) can be used to induce a cyclic weaving on the surface. In extended graph rotation systems, an edge is viewed as a paper strip that can be twisted. The sides of the paper strips provide ``two strands'' to construct weaving structures. Either these strands are ``parallel'' to the mesh edge for an ``untwisted edge'', or they both cross over the edge and over each other for a ``twisted edge''. If an arbitrary subset of edges of a mesh on an orientable surface is twisted in the same helical sense, then the EGRS induces a cyclic plain-weaving on the surface, which consists of cycles that cross other cycles (or themselves) by alternatingly going over and under. In this paper, we show that it is always possible to create a single-cycle plain-weaving starting from a mesh on an arbitrary surface, by selecting an appropriate subset of edges to be twisted. We also demonstrate how, starting from a mesh, to construct a large number of single-cycle plain-woven objects. Interestingly, the single-cycle solutions with a minimal number of edge twists correspond to plain-woven objects that are visually similar to Celtic knots. For converting plain-weaving cycles to 3D thread structures, we extend the original projection method, which previously worked only when all mesh edges are twisted. With the extension described here, our projection method can also be used to handle untwisted edges. We have developed a system that converts any manifold mesh into single-cycle plain-woven objects, by interactively controlling the proportion of edges that are twisted. The system also allows us to change the shapes of the threads with a set of parameters, interactively in real-time. We demonstrate here that by using this system, we can create a wide variety of single-cycle plain-woven objects.

In this paper, we show how to create plain-weaving over an arbitrary surface. To create a plain-weaving on a surface, we need to create cycles that cross other cycles (or themselves) by alternatingly going over and under. We use the fact that it is possible to create such cycles, starting from any given manifold-mesh surface by simply twisting every edge of the manifold mesh. We have developed a new method that converts plain-weaving cycles to 3D thread structures. Using this method, it is possible to cover a surface without large gaps between threads by controlling the sizes of the gaps. We have developed a system that converts any manifold mesh to a plain-woven object, by interactively controlling the shapes of the threads with a set of parameters. We have demonstrated that by using this system, we can create a wide variety of plain-weaving patterns, some of which may not have been seen before.

The computational complexity of constructing the imbeddings of a given graph into surfaces of different genus is not well understood. In this paper, topological methods and a reduction to linear matroid parity are used to develop a polynomial-time algorithm to find a maximum-genus cellular imbedding. This seems to be the first imbedding algorithm for which the running time is not exponential in the genus of the imbedding surface.

A hnear time algorithm to decide whether a given finite 2-complex is planar is described Topological results of Gross, Harary, and Rosen are the mathematical basis for the algorithm Opttmal running time is achieved by constructing various hsts simultaneously and keeping their ordermgs compatible If the complex is stmphcial with p vertices, then the algorithm has O(p) time and space bounds The algorithm uses depth-first search both m application of the graph plananty algorithm of Hopcroft and Tarjan and elsewhere