-
Linkage
It’s the last day of classes for the winter quarter here at UCI, and a good time for some spring cleaning of old bookmarked links. Probably also a good time for a reminder that Google+ is shutting down in two weeks so if, like me, you still have links to it then you don’t have long to replace them with archived copies before it gets significantly more difficult.
-
Planar graphs needing many lines
As I said in my previous post my two SoCG papers both involved trying and failing to prove something else, and writing down what I could prove instead. For the one that appears today, “Cubic planar graphs that cannot be drawn on few lines” (arXiv:1903.05256), that something else was Open Problem 16.14 of my book, which can be rephrased as: does there exist a family of planar graphs that cannot be drawn planarly with all vertices on a constant number of convex curves?
-
Counting polygon triangulations is hard
In some sense both of my accepted papers at SoCG are about a situation where I really wanted to prove something else, wasn’t able to, and wrote up what I could prove instead. The one whose preprint appears today, “Counting polygon triangulations is hard” (arXiv:1903.04737), proves that it’s -complete to count the triangulations of a polygon with holes.
-
Linkage
This seems like a good time to throw in a word of appreciation for archive.org and their wayback machine for making it so easy to make permanent links to online resources that might otherwise go away, such as other people’s Google+ posts. Just search for the link on archive.org and, if it’s not archived already, it will give you a convenient link to immediately archive it. There’s one of those hiding in the links below, and more among the older links on my blog.
-
Mutual nearest neighbors versus closest pairs
In the 1990s I published a series of papers on data structures for closest pairs. As long as you already know how to maintain dynamic sets of objects of some type, and answer nearest-neighbor queries among them, you can also keep track of the closest pair, and this can be used as a subroutine in many other computational geometry algorithms. But it turns out that many of those algorithms can now be simplified and sped up by using mutual nearest neighbors (pairs of objects that are each other’s nearest neighbors) instead of closest pairs.
-
Linkage
Beware the Ides of February.
-
Big convex polyhedra in grids
I recently wrote here about big convex polygons in grids, a problem for which we know very precise answers. This naturally raises the question: what about higher dimensions? How many vertices can be part of a convex polyhedron in an grid, or more generally a convex polytope in a -dimensional grid of side length ? Here we do still know some pretty good answers, at least up to constant factors in spaces of constant dimension.
-
Linkage
As usual, follow me on Mathstodon to see these as I post them rather than two weeks later.
-
Simplifying task-milestone diagrams
In my graph algorithms class last week, I covered critical path scheduling, as motivation for the linear-time algorithms for computing shortest and longest paths in directed acyclic graphs. In this scheduling problem, you are given a system of tasks, each with a predicted time to perform it, and constraints that some tasks should be done before others. Assuming that you have enough people working together to perform tasks in parallel, how quickly can you get everything done?
-
Orientations of infinite graphs
An orientation of an undirected graph is the directed graph that you get by assigning a direction to each edge. Several kinds of orientations have been studied. For instance, in a graph with even vertex degrees, an Eulerian orientation makes the numbers of incoming and outgoing degrees equal at each vertex. In a bridgeless graph, a strong orientation makes the resulting directed graph strongly connected. In finite connected graphs, every Eulerian orientation is strong, but that is untrue in infinite graphs. Consider, for instance, the graph of unit distances on the integers, which is Eulerian (every vertex has degree two) but has no strong orientation (every edge is a bridge). Even when a strong orientation exists, an Eulerian orientation might not be strong: the graph of distance-1 and distance-2 integers, with the orientation from smaller to larger numbers, is Eulerian but not strong. So when does an Eulerian strong orientation exist? The answer turns out to be: whenever the obvious obstacles are not present. Every bridgeless connected even-degree infinite graph has an Eulerian strong orientation.
subscribe via RSS