?

Log in

0xDE
If you draw a series-parallel multigraph in the plane, with an extra edge (the dashed edge below) connecting its two terminals, then its planar dual is also a drawing of the same type, turned sideways. The terminals of the dual are the vertices linked by the dual of the dashed edge. Each series composition in the primal turns into a parallel composition in the dual, and vice versa. Often one talks only about series-parallel graphs, not multigraphs, but for this duality the "multi" part is not easily avoidable: the primal or dual (or both) will have multiple edges between the same two vertices.



Read more...Collapse )
 
 
0xDE
17 May 2016 @ 04:14 pm

You may have heard of the Poincaré disk model of the hyperbolic plane, in which the whole hyperbolic plane is mapped to the interior of a Euclidean disk, with hyperbolic lines being transformed into circular arcs that make a right angle with the disk boundary. Or of the Beltrami–Klein model, which also maps the hyperbolic plane to the interior of a disk, but with a different map that keeps the lines straight, so that they correspond to the chords of a circle.

One use for these models is in information visualization, to provide a fisheye view of a drawing in the hyperbolic plane that provides "focus+context": focus on some specific feature in the drawing, and context of all the rest of the drawing, compressed into the outer parts of the disk. Another is as an aid to mathematical intuition: hyperbolic lines may be hard to visualize and understand, but chords of a circle are much more familiar, and this model shows that (in terms of the combinatorial patterns they can perform, if not their distances and angles) they are really the same thing.

But did you know that you can get an analogous fisheye view of the Euclidean plane, by another pair of models that map Euclidean lines to natural families of curves in a disk?

Read more...Collapse )
 
 
 
 
0xDE
30 April 2016 @ 07:58 pm
The image below is a study of the geometry of MIT's Kresge Auditorium.



Read more...Collapse )
 
 
0xDE
20 April 2016 @ 08:31 pm
Do you have a software project in which you need a fast and space-efficient approximate set data structure, like a Bloom filter? Then probably what you want is actually a cuckoo filter, a plug-in replacement for Bloom filters that is faster, more space-efficient, and more versatile (because it allows elements to be deleted as well as inserted).

Read more...Collapse )
 
 
0xDE
17 April 2016 @ 11:23 pm
At LATIN, Allan Borodin brought my attention to a recent paper of his with Yuli Ye, "Elimination graphs" (TALG 2012), about an idea that combines local properties of graphs with degeneracy.

Read more...Collapse )
 
 
0xDE
16 April 2016 @ 06:38 pm
I recently traveled to Ensenada (my first visit to Mexico, despite its closeness) for LATIN 2016. This was our view every morning on our arrival to CICESE, the research center hosting the conference, for the conference breakfast.



The rest of my photos include several from the conference excursion and dinner in the Valle de Guadalupe, Mexico's wine region.
 
 
0xDE
15 April 2016 @ 09:43 pm
I continue to find it ironic that the best way I can find to index my posts on Google+, a social network platform launched in 2011 by a major search engine company, and to make it possible for me to search for and find the old posts, is to copy them onto a much older social network platform from 1999 that, except for the Russians, has now mostly fallen into disuse.
 
 
 
0xDE

I recently asked my data structures class the following question: suppose you fill in an n-cell array by a random permutation. What is the probability that the result is a valid binary min-heap?

Read more...Collapse )
 
 
0xDE
18 March 2016 @ 09:07 pm
Some scenes near the entrance to the Bellairs Research Institute, in Holetown, Barbados. (You can see the institute's nameplate in the left background to this one). It's actually quite an upscale touristy town, but that wasn't the feeling I was trying to catch in these photos.



( More photos )
 
 
 
0xDE
14 March 2016 @ 10:35 am
I recently returned from the Fourth Annual Workshop on Geometry and Graphs at the Bellairs Research Institute in Barbados. The youngest participant was Günter Rote's daughter:



( More photos of workshop participants )
 
 
 
0xDE
When dealing with finite graphs, it's normal to define (rooted) trees in a graph-theoretic way: a tree is a directed graph with a designated root in which each vertex has a unique walk to the root. The ancestor-descendant relation can be derived from this: an ancestor of x is a vertex that can be reached by a walk from x. However, it's also possible to turn this around, and define trees in terms of their ancestor-descendant relations, with the parent-child relation derived from that. In the turned-around definition, a tree is a partial order with a designated root element that is a predecessor of every element, such that the predecessors of each element are totally ordered. The parent of an element would then be the maximum of its predecessors. So graph-theoretic finite trees and order-theoretic finite trees are really the same things as each other, in a different disguise. But that's no longer true when we go from finite to infinite: we can define trees in either of these two ways, but we get different things.

Read more...Collapse )
 
 
0xDE
16 February 2016 @ 10:12 pm
I spent the president's day holiday hiking in Black Star Canyon, a wilderness area nearby enough that it's barely outside Irvine and remote enough that in the upper part of the falls trail (where you're basically scrambling up a creek instead of hiking along a trail) there's no sign of civilization to be seen except for the other hikers, airplanes overhead, and occasional painted rocks.



( More photos of Black Star Canyon )
 
 
 
0xDE
I have a new preprint, "Distance-Sensitive Planar Point Location" (arXiv:1602.00767, with Aronov, de Berg, Roeloffzen, and Speckmann) whose title and abstract may already be a bit intimidating. So I thought I would at least try to explain what it's about in simpler terms.

Read more...Collapse )