September 21, 2014

1:05 AM | Which polycubes have planar graphs?
Joe Malkevitch recently asked me: which polycubes have planar graphs?By a polycube, I mean a set of unit cubes in the three-dimensional integer lattice whose dual graph (with vertices for cubes and edges for cubes that share a square with each other) is connected; Malkevitch had a more restrictive definition in mind in which the boundary of the union of the cubes is a connected manifold, but that turns out not to make a difference for this problem. The graph of a polycube is formed by the […]

September 16, 2014

6:20 AM | Linkage
Unexpected shapes in smoke plumes, as photographed by Thomas Herbrich (G+)ISAAC 2014 and COCOA 2014 accepted paper lists (G+)FOCS 2014 program and best paper winners (G+)Kinetic sculpture made of wooden balls on threads, with some extensive software simulation behind its design (G+)How a 19th century math genius taught us the best way to hold a pizza slice, or, a practical application of the theorem that when a flat surface is embedded in 3d, it remains flat in at least one direction […]

September 13, 2014

9:57 PM | Bren Hall, East Stairs
Just some test shots with my new travel lens (Canon's 17-40/F4 L, replacing a mysteriously nonfunctional and optically not as good 17-85IS).

September 10, 2014

5:15 AM | Algorithmic representative democracy
Did you ever wonder why different states of the US have the numbers of representatives in congress that they do? It's supposed to be proportional to population but that's not actually true: for instance the ratio of representatives to population is about 40% higher in Montana than California. What formula or algorithm do they use to pick the numbers?This has varied over the years but, Wikipedia tells me, currently it's the Huntington–Hill method. One way of describing this is by a simple […]

September 06, 2014

6:47 AM | Efficiency of Rado graph representations
The Rado graph has interesting symmetry properties and plays an important role in the logic of graphs. But it's an infinite graph, so how can we say anything about the complexity of algorithms on it?There are algorithmic problems that involve this graph and are independent of any representation of it, such as checking whether a first-order logic sentence is true of it (PSPACE-complete). But I'm interested here in problems involving the Rado graph where different ways of constructing and […]

September 01, 2014

5:59 AM | Linkage
More Google+ links from the last couple of weeks:An interview with Haida artist Jim Hart (G+):Persi Diaconis discusses mathematics and magic (G+)A still-unsolved question about whether it's possible to compute edit distance in sublinear space and polynomial time (G+)A New York Times story about how scheduling software makes part-time workers' lives harder. Or does it? The MF discussion of the article makes it clear that managers have been doing the same things with lower tech for a long time. […]

August 29, 2014

5:46 AM | Flattening things that aren't already flat
The last of my Graph Drawing preprints is also the first of the papers to see daylight from the workshop last spring in Barbados: "Flat Foldings of Plane Graphs with Prescribed Angles and Edge Lengths" (arXiv:1408.6771, with Zachary Abel, Erik Demaine, Martin Demaine, Anna Lubiw, and Ryuhei Uehara).It's part of what has become a long line of research on trying to understand which shapes can be squashed flat, starting with Maekawa's theorem (every vertex of a flat-folded sheet of paper has to […]

August 28, 2014

12:43 AM | A brief introduction to the logic of graphs
If you're used to writing mathematics, but haven't paid much attention to model theory, you probably think a fully-quantified mathematical sentence is generally either true or false. Fermat's last theorem, for instance, can be written as the following sentence: For all positive integers a, b, c, and n, if n > 2, then an + bn ≠ cn. This sentence is fully quantified: the four variables a, b, c, and n are all covered by the quantifier "for all positive […]

August 27, 2014

5:35 AM | Planarization by vertex deletion
Another of my Graph Drawing papers is online today: "Planar Induced Subgraphs of Sparse Graphs", arXiv:1408.5939, with Cora Borradaile and her student Pingan Zhu. It's about finding large planar subgraphs in arbitrary graphs; in the version of the problem we study, we want the planar subgraph to be an induced subgraph, so the goal is to find as large a subset of vertices as possible with the property that all edges connecting them can be drawn planarly. Equivalently, we want to delete as few […]

August 22, 2014

6:16 AM | Circle packings with small area
The second of my papers for this year's Graph Drawing symposium is now online: "Balanced Circle Packings for Planar Graphs", arXiv:1408.4902, with Jawaherul Alam, Mike Goodrich, Stephen Kobourov, and Sergey Pupyrev. It's about finding circle packings (interior-disjoint circles whose tangencies form a given graph) where the radii are all within a polynomial factor of each other. Or equivalently, if one normalizes the packing to make the smallest circles have unit radius, then the area of the […]
10 Results