0xDE
28 August 2014 @ 10:46 pm
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).

Read more...Collapse )
 
 
0xDE
27 August 2014 @ 05:43 pm
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 integers". It's one of the true ones, if difficult to prove.

But when we're working with the logic of graphs, a (fully-quantified) sentence is itself just another mathematical object, and its truth is relative: it might be true for some graphs and false for others. Read more...Collapse )
 
 
0xDE
26 August 2014 @ 10:35 pm
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 vertices as possible to make the remaining graph planar. It's NP-complete, of course, so our goal is to prove good bounds on how many vertices you need to delete rather than computing this number exactly.

Read more...Collapse )
 
 
0xDE
21 August 2014 @ 11:16 pm
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 packing should be at most polynomial. We call packings with this property "balanced".

Read more...Collapse )
 
 
0xDE
18 August 2014 @ 05:22 pm
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 nomination and voting involved a group of fans from one of the subgenres of SF whose two main interests seem to be military jingoism and sexual and racial anti-inclusivity and who have apparently dubbed themselves the "sad puppies". These people pushed a slate of nominees onto the ballot, which then lost fairly decisively in the final voting. There was no unfair vote manipulation going on: everything was aboveboard and according to the rules. But it caused me to wonder: how large would a dedicated faction of the voters have to be to break into the winner's circle, against the will of the remaining voters?

Read more...Collapse )
Tags:
 
 
0xDE
15 August 2014 @ 10:00 pm
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):
Tags:
 
 
0xDE
14 August 2014 @ 11:51 pm
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 Afro-Cuban art including two sculptures shown above. Definitely worth a visit if you're in the Vancouver area, despite the minor inconvenience of getting there from downtown (we took a city bus).
 
 
0xDE
10 August 2014 @ 09:13 pm
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 makes the image very static. But when I cropped the shot (mostly to put it into this panoramic aspect ratio) the tree insisted that that's where it had to be. I don't understand why. Also, the small bush on the right, that seems like a distraction, is necessary. I had another version of this image from a slightly different perspective that eliminated the bush, and it didn't work as well. Again, I can't explain why.

Some other Vancouver stuff I enjoyed but didn't photograph: visiting artists' studios, sampling artisinal sake, and learning about summer tree-planting jobs from another sake taster, on Granville Island (do it on a weekday); Shakespeare in the park (The Tempest, but they're also showing Midsummer Night's Dream if you haven't already seen that one more times than you can count); sushi at Miku (across the street from my hotel) and bubble tea next door (we have plenty of that at home but this one had even more variety); Douglas Coupland's big art show at the Vancouver Art Gallery (apparently he's not just a famous author); and waffles and berries for breakfast (there are several cafes that specialize in this — the one we chose was on Pender between Nicola and Broughton).
 
 
0xDE
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. Read more...Collapse )
 
 
0xDE
08 August 2014 @ 12:28 am
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 polygon in the plane, formed by rigid line segments connected to each other by flexible hinges at the vertices, adjust the angles of the polygon to surround the maximum area possible. What is the shape of the optimal solution?

Read more...Collapse )
 
 
0xDE

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 names would be welcome on the site, and (as one very minor consequence) I stopped posting there. Now, finally, Google+ has relented and will allow arbitrary user-chosen identities. They could have been more apologetic about it, but it's enough for me to return there.

I don't intend to change my Livejournal posting habits much, as I've been using my Google+ account for a somewhat different purpose: posting brief links to web sites that catch my attention and that I think might be of interest to my (mostly technical/academic) circles of contacts there. Here's a roundup of a dozen or so links I've posted so far (skipping the ones where I linked back to my LJ postings).

 
 
0xDE
26 July 2014 @ 11:04 pm
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 )
 
 
0xDE
26 July 2014 @ 06:57 pm
Aka that wide spot in the road on the way to Montgomery Woods



( More )
 
 
0xDE
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 be true.



Read more...Collapse )
 
 
0xDE
21 July 2014 @ 04:54 pm
The diagram below describes a finite state machine that takes as input a description of an indifference graph, and produces as output a 1-planar drawing of it (that is, a drawing with each edge crossed at most once).



Read more...Collapse )
 
 
0xDE
11 July 2014 @ 08:25 pm
I noticed that there was a higher-than-usual density of arxiv preprints among the web pages I'd been bookmarking lately, so I thought maybe I'd share. The first one, especially, is very timely:

Soccer balls and graph theoryCollapse )

Scenic routingCollapse )

Convex puzzle rearrangementCollapse )

Which subgraphs can be counted quickly?Collapse )
 
 
0xDE
05 July 2014 @ 11:07 pm
For the past month or so, until this weekend when they moved out, we've had some squatters on our front porch: a family of Black Phoebes. They conveniently set up their nest in clear sight of a window over the front door, through which I could aim the camera.

 
 
0xDE
02 July 2014 @ 09:38 am
Via MIT's news office I learn that Seth Teller has died, at the young age of 50. Seth primarily worked in robotics and vision, but was also a regular participant at the Symposium on Computational Geometry. For more about his many accomplishments, read the MIT story.

ETA: Scott Aaronson has more
 
 
0xDE
29 June 2014 @ 10:21 pm
One of Wikipedia's less well-known features is its Book: namespace. The things there are called books, and they could be printed on paper and bound into a book if you're one of those rare Wikipedia users who doesn't use a computer to read things, but really they're curated collections of links to Wikipedia articles. I've made two of them before, Book:Graph Algorithms and Book:Fundamental Data Structures, which I have used for the readings in my graduate classes on those topics because I wasn't satisfied with the textbooks on those subjects. This week I put together a third one, Book:Graph Drawing.

It's not complete (what on Wikipedia is?), and the writing quality and depth of coverage are as variable as always, but there are about 100 topics there and I hope that collecting them in this way proves useful. I've listed a few more things that I think should be added but don't yet have their own Wikipedia articles on the talk page, but if you see something else missing then please let me know or, even better, add it.
 
 
0xDE
27 June 2014 @ 02:18 pm
Voting opened this week for members of the compgeom-announce mailing list, on whether the annual Symposium on Computational Geometry should leave ACM, as the Conference on Computational Complexity has recently done from IEEE.

There's a lot more opinion on both sides of the issue, and arguments both for staying with ACM and for leaving, in a series of postings at MakingSoCG. If you're a compgeom-announce member, please inform yourself and then make your own opinion known through the vote. Past votes on the same issue had unconvincing results due to low turnout; we don't want the same problem to happen again.