Search

We present a method for proving upper bounds on the eigenvalues of the graph Laplacian. A main step involves choosing an appropriate 'Riemannian' metric to uniformize the geometry of the graph. In many interesting cases, the existence of such a metric is shown by examining the combinatorics of special types of flows. This involves proving new inequalities on the crossing number of graphs. In particular, we use our method to show that for any positive integer k, the k [superscript th] smallest eigenvalue of the Laplacian on an n-vertex, bounded-degree planar graph is O(k/n). This bound is asymptotically tight for every k, as it is easily seen to be achieved for square planar grids. We also extend this spectral result to graphs with bounded genus, and graphs which forbid fixed minors. Previously, such spectral upper bounds were only known for the case k = 2., National Science Foundation (U.S.) (NSF grant CCF-0843915), National Science Foundation (U.S.) (NSF grant CCF-0915251), National Science Foundation (U.S.) (grant CCF-0644037), National Science Foundation (U.S.) (Graduate Research Fellowship), Akamai Technologies, Inc., Alfred P. Sloan Foundation (Research Fellowship), National Science Foundation (U.S.) (NSF grant CCF-0635102), National Science Foundation (U.S.) (grant CCF-0964481), National Science Foundation (U.S.) (CCF-1111270)

We present a method for proving upper bounds on the eigenvalues of the graph Laplacian. A main step involves choosing an appropriate 'Riemannian' metric to uniformize the geometry of the graph. In many interesting cases, the existence of such a metric is shown by examining the combinatorics of special types of flows. This involves proving new inequalities on the crossing number of graphs. In particular, we use our method to show that for any positive integer k, the k [superscript th] smallest eigenvalue of the Laplacian on an n-vertex, bounded-degree planar graph is O(k/n). This bound is asymptotically tight for every k, as it is easily seen to be achieved for square planar grids. We also extend this spectral result to graphs with bounded genus, and graphs which forbid fixed minors. Previously, such spectral upper bounds were only known for the case k = 2., National Science Foundation (U.S.) (NSF grant CCF-0843915), National Science Foundation (U.S.) (NSF grant CCF-0915251), National Science Foundation (U.S.) (grant CCF-0644037), National Science Foundation (U.S.) (Graduate Research Fellowship), Akamai Technologies, Inc., Alfred P. Sloan Foundation (Research Fellowship), National Science Foundation (U.S.) (NSF grant CCF-0635102), National Science Foundation (U.S.) (grant CCF-0964481), National Science Foundation (U.S.) (CCF-1111270)

We prove that the pleated hyperbolic paraboloid, a familiar origami model known since 1927, in fact cannot be folded with the standard crease pattern in the standard mathematical model of zero-thickness paper. In contrast, we show that the model can be folded with additional creases, suggesting that real paper “folds” into this model via small such creases. We conjecture that the circular version of this model, consisting simply of concentric circular creases, also folds without extra creases. At the heart of our results is a new structural theorem characterizing uncreased intrinsically flat surfaces—the portions of paper between the creases. Differential geometry has much to say about the local behavior of such surfaces when they are sufficiently smooth, e.g., that they are torsal ruled. But this classic result is simply false in the context of the whole surface. Our structural characterization tells the whole story, and even applies to surfaces with discontinuities in the second derivative. We use our theorem to prove fundamental properties about how paper folds, for example, that straight creases on the piece of paper must remain piecewise-straight (polygonal) by folding., National Science Foundation (U.S.) (CAREER Award CCF-0347776)

A convex surface that is flat everywhere but on finitely many smooth curves (or seams) and points is a seam form. We show that the only creases through the flat components of a seam form are either between vertices or tangent to the seams. As corollaries we resolve open problems about certain special seam forms: the flat components of a D-form have no creases at all, and the flat component of a pita-form has at most one crease, between the seam’s endpoints., National Science Foundation (U.S.) (CAREER award CCF-0347776), United States. Dept. of Energy (grant DE-FG02-04ER25647), United States. Air Force Office of Scientific Research (grant FA9550-07-1-0538), National Science Foundation (U.S.) (Graduate Research Fellowship)

Alexandrov’s Theorem states that every metric with the global topology and local geometry required of a convex polyhedron is in fact the intrinsic metric of some convex polyhedron. Recent work by Bobenko and Izmestiev describes a differential equation whose solution is the polyhedron corresponding to a given metric. We describe an algorithm based on this differential equation to compute the polyhedron to arbitrary precision given the metric, and prove a pseudopolynomial bound on its running time., National Science Foundation (U.S.) (Career award CCF-0347776), National Science Foundation (U.S.). Graduate Research Fellowship Program

Alexandrov’s Theorem states that every metric with the global topology and local geometry required of a convex polyhedron is in fact the intrinsic metric of some convex polyhedron. Recent work by Bobenko and Izmestiev describes a differential equation whose solution is the polyhedron corresponding to a given metric. We describe an algorithm based on this differential equation to compute the polyhedron to arbitrary precision given the metric, and prove a pseudopolynomial bound on its running time., National Science Foundation (U.S.) (Career award CCF-0347776), National Science Foundation (U.S.). Graduate Research Fellowship Program

A convex surface that is flat everywhere but on finitely many smooth curves (or seams) and points is a seam form. We show that the only creases through the flat components of a seam form are either between vertices or tangent to the seams. As corollaries we resolve open problems about certain special seam forms: the flat components of a D-form have no creases at all, and the flat component of a pita-form has at most one crease, between the seam’s endpoints., National Science Foundation (U.S.) (CAREER award CCF-0347776), United States. Dept. of Energy (grant DE-FG02-04ER25647), United States. Air Force Office of Scientific Research (grant FA9550-07-1-0538), National Science Foundation (U.S.) (Graduate Research Fellowship)

We present a general method for proving upper bounds on the eigenvalues of the graph Laplacian. In particular, we show that for any positive integer k, the kth smallest eigenvalue of the Laplacian on a bounded-degree planar graph is O(k/n). This bound is asymptotically tight for every k, as it is easily seen to be achieved for planar grids. We also extend this spectral result to graphs with bounded genus, graphs which forbid fixed minors, and other natural families. Previously, such spectral upper bounds were only known for k = 2, i.e. for the Fiedler value of these graphs. In addition, our result yields a new, combinatorial proof of the celebrated result of Korevaar in differential geometry., National Science Foundation (U.S.) (CCF-0843915), National Science Foundation (U.S.) (CCF-0644037), National Science Foundation (U.S.) (CCF-0635102), Akamai Technologies, Inc., National Science Foundation (U.S.). Graduate Research Fellowship Program

We present a general method for proving upper bounds on the eigenvalues of the graph Laplacian. In particular, we show that for any positive integer k, the kth smallest eigenvalue of the Laplacian on a bounded-degree planar graph is O(k/n). This bound is asymptotically tight for every k, as it is easily seen to be achieved for planar grids. We also extend this spectral result to graphs with bounded genus, graphs which forbid fixed minors, and other natural families. Previously, such spectral upper bounds were only known for k = 2, i.e. for the Fiedler value of these graphs. In addition, our result yields a new, combinatorial proof of the celebrated result of Korevaar in differential geometry., National Science Foundation (U.S.) (CCF-0843915), National Science Foundation (U.S.) (CCF-0644037), National Science Foundation (U.S.) (CCF-0635102), Akamai Technologies, Inc., National Science Foundation (U.S.). Graduate Research Fellowship Program

We present a method for proving upper bounds on the eigenvalues of the graph Laplacian. A main step involves choosing an appropriate "Riemannian" metric to uniformize the geometry of the graph. In many interesting cases, the existence of such a metric is shown by examining the combinatorics of special types of flows. This involves proving new inequalities on the crossing number of graphs. In particular, we use our method to show that for any positive integer k, the kth smallest eigenvalue of the Laplacian on an n-vertex, bounded-degree planar graph is O(k/n). This bound is asymptotically tight for every k, as it is easily seen to be achieved for square planar grids. We also extend this spectral result to graphs with bounded genus, and graphs which forbid fixed minors. Previously, such spectral upper bounds were only known for the case k=2.

We prove that the pleated hyperbolic paraboloid, a familiar origami model known since 1927, in fact cannot be folded with the standard crease pattern in the standard mathematical model of zero-thickness paper. In contrast, we show that the model can be folded with additional creases, suggesting that real paper "folds" into this model via small such creases. We conjecture that the circular version of this model, consisting simply of concentric circular creases, also folds without extra creases. At the heart of our results is a new structural theorem characterizing uncreased intrinsically flat surfaces--the portions of paper between the creases. Differential geometry has much to say about the local behavior of such surfaces when they are sufficiently smooth, e.g., that they are torsal ruled. But this classic result is simply false in the context of the whole surface. Our structural characterization tells the whole story, and even applies to surfaces with discontinuities in the second derivative. We use our theorem to prove fundamental properties about how paper folds, for example, that straight creases on the piece of paper must remain piecewise-straight (polygonal) by folding., Comment: 19 pages, 6 figures

Alexandrov's Theorem states that every metric with the global topology and local geometry required of a convex polyhedron is in fact the intrinsic metric of a unique convex polyhedron. Recent work by Bobenko and Izmestiev describes a differential equation whose solution leads to the polyhedron corresponding to a given metric. We describe an algorithm based on this differential equation to compute the polyhedron to arbitrary precision given the metric, and prove a pseudopolynomial bound on its running time. Along the way, we develop pseudopolynomial algorithms for computing shortest paths and weighted Delaunay triangulations on a polyhedral surface, even when the surface edges are not shortest paths., Comment: 25 pages; new Delaunay triangulation algorithm, minor other changes; an abbreviated v2 was at WADS 2009

A convex surface that is flat everywhere but on finitely many smooth curves (or "seams") and points is a seam form. We show that the only creases through the flat components of a seam form are either between vertices or tangent to the seams. As corollaries we resolve open problems about certain special seam forms: the flat components of a D-form have no creases at all, and the flat component of a pita-form has at most one crease, between the seam's endpoints., Comment: revised