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

August 01, 2014

4:02 AM | A victory in the Nymwars and some Google+ links
The nymwars are the struggle to maintain online safe havens for pseudonymous free speech, for people who don't feel safe linking their opinions with their real names (for fear of religious persecution / sexual predation / current or future job prospects / whatever else) in the face of attempts by Facebook, Google, and others to force everyone to cross-link all their personal information. Soon after its launch in 2011, Google+ took a strong stand that only people willing to post under their real […]

July 27, 2014

6:04 AM | Montgomery Woods
Until 2006 (when bigger ones were found elsewhere) this was the home to the tallest known tree in the world. But it's not marked, so you just have to look at them all and guess which one might be the biggest.( More )
1:57 AM | Comptche
Aka that wide spot in the road on the way to Montgomery Woods( More )

July 24, 2014

12:50 AM | Big grids in outerplanar strict confluent graphs
I was wondering whether the outerplanar strict confluent drawings I studied in a Graph Drawing paper last year had underlying diagrams whose treewidth is bounded, similarly to the treewidth bound for the usual outerplanar graphs. The confluent graphs themselves can't have low treewidth, because they include large complete bipartite graphs, but I was hoping that a treewidth bound for the diagram could be used to prove that the graphs themselves have low clique-width. Sadly, it turns out not to […]
11 Results