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 […]

August 19, 2014

12:22 AM | Condorcet, Hugo, and sad puppies
Yesterday, this year's Hugo Award winners were announced; this is an annual fan popularity contest for the best works in science fiction and fantasy (there is a different set of awards voted on by the writers themselves, the Nebulas). I have a few thoughts on the nominees (like, why wasn't Her among them?) but that's not what I'm writing about. Rather, what interests me in this year's contest is the issue of voting systems and their resistance to manipulation.Some background: this year's award […]

August 16, 2014

4:59 AM | Linkage
Some links I've posted over on Google+ over the last couple of weeks (and reposted here, among other reasons, because I don't trust G+ to give me a usable interface for finding all of my old posts there): {7,3,3} Honeycomb, an interesting polyhedral tesselation of hyperbolic space with a fractal boundary (G+) How to distort school rankings in your favor (G+) Some impressive fisheye photography of the heavily patterned interiors of Iranian mosques (G+) A brief history of mazes and labyrinths, […]

August 15, 2014

6:51 AM | Museum of Anthropology
My photos from the UBC Museum of Anthropology are online now. Here is a sampling of thumbnails: The museum is mostly devoted to Pacific Northwest First Nations art, but as a living culture rather than as something that happened in the past, so it includes a mix of older cultural artifacts with more modern art. It also has a gallery of Pacific Rim cultures, and a couple of rotating exhibit spaces; for our visit, one of them was on "urban aboriginal youth" and the other was a show of […]

August 11, 2014

4:13 AM | Jun Ren, Freezing Water #7, Vanier Park
I just returned from a short vacation in Vancouver (unrelated to SIGGRAPH, also happening there now) and took a few snapshots, mostly of boats or totem poles. Another batch of photos from MOA, also with many totem poles, is still to come. But here's one that has neither:Obviously, I don't understand the rules of photographic composition. By any rational standard, the tree should not be at the center. It's not the subject, it attracts too much attention to itself there, and centering typically […]

August 10, 2014

2:13 AM | Three-colorable circle graphs and three-page book embeddings
The GD11 contest graph that I've written about earlier turns out to be a circle graph. Here's a chord diagram representing it:I'm looking at this and similar graphs because I'm trying to understand a result claimed in a STACS 1992 paper by Walter Unger, "The Complexity of Colouring Circle Graphs", which claims that testing 3-colorability of circle graphs can be done in polynomial time. (More precisely Unger claims a time bound of O(n log n) if a chord diagram representing the graph […]

August 08, 2014

7:28 AM | Queen Dido and the carpenter's rule
The story goes that Dido, a refugee from her home city of Tyre, took refuge in north Africa where king Iarbas granted her and her followers a small amount of land: the amount that she could surround by an oxhide. Cleverly, she cut the hide into a cord, which she arranged in a circle around a hill to maximize the area it would surround, and in so doing founded the city of Carthage. But what if Dido had been granted a carpenter's rule instead of an oxhide? Mathematically, the problem is: given a […]
11 Results