• Euler characteristics of non-manifold polycubes

    From a block of cubes, remove two non-adjacent and non-opposite cubes. The resulting polycube has a boundary that is not a manifold: between the two removed cubes, there is an edge shared by four squares, but a two-dimensional manifold can only have two faces per edge. Nevertheless, we can compute its Euler characteristic as the number of vertices () minus the number of edges () plus the number of square faces (). , the same number we would expect for the Euler characteristic of a topological sphere! What does it mean?

  • Linkage

  • Monochromatic grids in colored grids

    Color the points of an grid with two colors. How big a monochromatic grid-like subset can you find? By “grid-like” I mean that it should be possible to place equally many horizontal and vertical lines, partitioning the plane into cells each of which contains a single point.

  • Coloring kinggraphs

    Draw a collection of quadrilaterals in the plane, meeting edge to edge, so that they don’t surround any open space (the region they cover is a topological disk) and every vertex interior to the disk touches at least four quadrilaterals. Is it always possible to color the corners of the quadrilaterals with four colors so that all four colors appear in each quadrilateral?

  • Photos from Barbados

    I spent this year’s spring break at Erik Demaine’s annual computational geometry workshop in Barbados again. A few photos of workshop participants:

  • Linkage

  • Linkage

    It’s the last day of classes for the winter quarter here at UCI, and a good time for some spring cleaning of old bookmarked links. Probably also a good time for a reminder that Google+ is shutting down in two weeks so if, like me, you still have links to it then you don’t have long to replace them with archived copies before it gets significantly more difficult.

  • Planar graphs needing many lines

    As I said in my previous post my two SoCG papers both involved trying and failing to prove something else, and writing down what I could prove instead. For the one that appears today, “Cubic planar graphs that cannot be drawn on few lines” (arXiv:1903.05256), that something else was Open Problem 16.14 of my book, which can be rephrased as: does there exist a family of planar graphs that cannot be drawn planarly with all vertices on a constant number of convex curves?

  • Counting polygon triangulations is hard

    In some sense both of my accepted papers at SoCG are about a situation where I really wanted to prove something else, wasn’t able to, and wrote up what I could prove instead. The one whose preprint appears today, “Counting polygon triangulations is hard” (arXiv:1903.04737), proves that it’s -complete to count the triangulations of a polygon with holes.

  • Linkage

    This seems like a good time to throw in a word of appreciation for archive.org and their wayback machine for making it so easy to make permanent links to online resources that might otherwise go away, such as other people’s Google+ posts. Just search for the link on archive.org and, if it’s not archived already, it will give you a convenient link to immediately archive it. There’s one of those hiding in the links below, and more among the older links on my blog.

subscribe via RSS