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.
 
 
0xDE
26 June 2014 @ 10:02 pm
It must be graduation-and-moving-out time again. Seen this morning, in the parking lot of a UCI apartment complex for postdocs and visiting researchers:

 
 
0xDE
03 June 2014 @ 10:33 pm
While cleaning up some badly-sourced articles on Wikipedia, I ran across the one on reverse perspective, a strange drawing style in which nearby objects are shown as small and far-away objects are shown as big. Despite the strangeness, it's mathematically consistent: it's what you get when you put objects between the perspective point (your eye in conventional perspective) and the viewing plane (a window through which you're looking at the world). Here's a nice example:



Although it's been used a lot in art (sometimes deliberately, for effect, sometimes naively, and sometimes for reasons lost to history and hotly debated), I don't know of any attempts to use it for visualization. It has some effects that might be useful, notably the ability to see more sides of an object at once than is possible in a conventional view.
 
 
0xDE
25 May 2014 @ 11:59 am
PADS, my collection of Python algorithm implementations, has finally been updated to work under both Python 2 and Python 3. Most, but not all, of its modules have been tested under both version of Python.

Most of the code was already pretty close to working. The most frequent changes I needed to do: use next(iterator) instead of iterator.next(); avoid xrange, iteritems, and itervalues; use list(dict.items) for loops that change the dictionary; wrap arguments to print in parens.
Tags:
 
 
0xDE
It must be that time of year...Friday and today I took part in two more thesis defenses, for Brian Parrish and Paweł Pszona.

Brian is a mechanical engineering student, supervised by fellow Wikipedia editor Mike McCarthy. His thesis research was to develop a system that can automatically analyze the configuration space of an eight-bar linkage and determine whether it can smoothly move between a desired set of poses. Somehow I got involved because setting up a system of equations describing the motion of these linkages involves some interesting graph algorithm problems. He's been working at Northrop Grumman, who supported him through his doctorate, and I imagine will continue working for them afterward.

Paweł is a theoretical computer scientist, supervised by Mike Goodrich. The topics he included in his thesis were external-memory approximation of graph degeneracy, applications of list labeling in the visualization of dynamic graphs, and three-dimensional arc diagrams. For the third of these topics, he brought along some props, 3d prints of his graph visualizations, which I think make the graph structure much clearer than their 2d projections. He has also done some interesting work with Goodrich (not part of his thesis) on making parametric search practical, and very recently published another paper with me and others on cuckoo hashing on storage devices with limited rewrite capacity. After he finishes he will be joining navigation-system company TomTom in Berlin.

Congratulations, both of you!
 
 
0xDE
18 May 2014 @ 08:09 pm


Despite the name, it's not a university facility; it's a nearby mall with a nice Cuban restaurant in it. The stripy building is also a restaurant, but not one I've tried.
 
 
0xDE
11 May 2014 @ 03:07 pm
Here's a graph drawing problem I don't know how to solve: find the smallest 3-regular graph that is not 1-planar.

Read more...Collapse )
 
 
0xDE
09 May 2014 @ 10:46 pm
Today, Joe Simons (a joint advisee of Mike Goodrich and me) passed his thesis defense. Most of my own research with Joe has been on graph drawing, but his dissertation concerned several results on different models of time in dynamic geometric data structures, including the retroactive model (in which updates you make to past versions of the timeline have effects that propagate through other more recent updates), the windowed model (in which you have to aggregate the events that happened within a query window of time into a larger structure), and the local-update model (in which objects can move, but only proportionally to their size). Joe has accepted a position at Google starting this summer.
 
 
0xDE
08 May 2014 @ 11:57 pm
Via the Process Algebra Diary, I learned of a recent paper by Andreas Björklund and Thore Husfeldt, Shortest Two Disjoint Paths in Polynomial Time, which just won the Track A best paper award at ICALP. It looks like a very interesting paper; I can see why it won the award.

Here's the problem it solves: you're given a graph with two pairs of terminals s1t1 and s2t2. The goal is to find disjoint paths connecting the two pairs of terminals with minimum total cost. It almost sounds like the problem solved by Suurballe's algorithm, but that one allows either s to be connected to either t, while here we have to connect the correct pairs. The specific version of this problem they solve is for undirected and unweighted graphs, with disjointness meaning either that the paths share no vertices or that they can share vertices but not edges. The unweighted part could easily be modified to paths weighted by small integers. Directed or real-weighted versions would also be natural but I don't know what's known about them and I don't think this paper's ideas are likely to work for them.

Read more...Collapse )
 
 
0xDE
27 April 2014 @ 10:22 pm
I found this parachute rat in Costa Mesa today. I have no idea whether it's authentic — the lack of detail kind of suggests it isn't, but given the history of the artist in question, how meaningful is authenticity anyway?



Not coincidentally, but perhaps ironically given the subject matter, almost exactly a year ago I recommended a Korean time travel movie, Young Gun In The Time, which sadly still seems very difficult to find. This year's time travel movie recommendation is for an Australian romance, The Infinite Man. Tightly plotted, quite stage-play-like in its very sparse cast and setting, darkly funny, and in some ways reminiscent of Rashomon in the way it keeps bringing in unexpectedly different viewpoints to the same repeated scenes. I enjoyed it. There's still still another chance to see it this coming Wednesday, if you're local, interested, and lacking your own time machine.
 
 
0xDE
21 April 2014 @ 11:33 am
I just added a new article to Wikipedia on indifference graphs (also known as unit interval graphs or proper interval graphs): the graphs formed from sets of points on the real line by connecting every two points whose distance is less than one.



There are many papers on algorithms for going from the graph to a geometric representation in linear time. The following method for the reverse problem, going from the set of points (or equivalently unit intervals) to its graph must be known, possibly in the context of its generalization to higher dimensional unit disk graphs, but I don't know a good reference for it.

Read more...Collapse )

Update, April 22: It appears that the correct reference for this is Bentley, Jon L.; Stanat, Donald F.; Williams, E. Hollins, Jr.
The complexity of finding fixed-radius near neighbors. Information Processing Lett. 6 (1977), no. 6, 209–212.
 
 
0xDE
19 April 2014 @ 02:07 pm
As I promised earlier, here is the video for my talk on "structures in solution spaces" at the Conference on Meaningfulness and Learning Spaces last February.



It was a wide-ranging talk, about learning spaces, distributive lattices and Birkhoff's representation theorem for them, rectangular cartograms, antimatroids, the 1/3-2/3 conjecture for partial orders and antimatroids, partial cubes, and flip distance in binary trees and point sets. It was also about an hour long, so don't watch unless you have the time. For those with shorter attention spans, I've also put up a pdf file of my talk slides.

The rest of the talks from the conference are also online. For those who like me are interested in discrete mathematics and discrete algorithms, Fred Roberts' talk on when the output of an algorithm is meaningful and Jean-Paul Doignon's talk on polyhedral combinatorics might be particularly interesting.
 
 
0xDE
13 April 2014 @ 11:50 pm
Every year about this time, my campus holds a spring celebration, with all the student organizations setting up pavilions in the park to sell food and advertise for new members, with the creative anachronists bashing each other with padded swords, and with a car show. Why a car show? I don't know, but I always enjoy seeing the variety of shapes and colors compared to today's mostly-the-same boxes. My favorite this year was a 1950 Chevy Fleetline, found rusting in a swamp in Tenessee; after a lot of work restoring it, its owner decided to cover it in clear-coat, showing off the patina on its metal, rather than just painting it. And then drove it cross country, towing a trailer full of his stuff, to UCI where his girlfriend is a grad student.



The moustache is more visible in this one. And here are the rest of the photos.
 
 
0xDE
12 April 2014 @ 10:07 pm
When I last saw Tetsuo Asano, he was giving a research talk at WADS, and openly worrying that it might be his last one. We all thought it was because of mandatory retirement (still legal in Japan). But, it turns out, no. Instead, he's the new president of JAIST. Congratulations, Tetsuo!

I'll probably miss SoCG, in Kyoto this year, but for those who will be going, there will be an associated workshop in honor of Asano's 65th birthday.