-
Splines for graph drawing theory
For a long time there has been a tension in graph drawing between theoretical and practical methods. Typical theoretical results show that graphs in certain special classes can be drawn with guaranteed bounds on certain measures of the drawing quality: for instance, the edges may be shaped as polylines with a hard limit on the number of bends per polyline, on the number of crossings per edge, and on the angle of each crossing. In practice we just want to draw arbitrary graphs and produce something legible. Few crossings and avoiding sharp angles are still good, but polylines are not: it can be difficult to distinguish bends from vertices or follow edges that repeatedly bend. For this reason, when straight line segments are inadequate, practical heuristics often use smooth curves rather than polylines, and especially spline curves.
-
Linkage
- Possibly all the ways to get loop-finding in graphs wrong (\(\mathbb{M}\)). Simon Tatham tries various ways of finding the edges of a graph that belong to at least one cycle, with bugs of various levels of sophistication, until finally settling on Tarjan’s bridge-finding algorithm. The application: checking puzzle solutions.
-
Computational complexities of folding
I turned my talks at OSME and JCGCG3 this summer into a paper: “Computational Complexities of Folding”, arXiv:2410.07666. It includes the following results:
-
A half-flipped binary tiling
In this tiling of the hyperbolic plane, all of the tiles are the same shape and size (despite their varied appearance), they are not square, and they are not polygons.
-
Linkage for the start of another academic year
- Shift networks (\(\mathbb{M}\)). Jeremy Kun asks how to permute vectors using few vector additions, elementwise multiplications, and rotation operations, for an application involving homomorphic encryption.
-
Long but non-crossing paths and cycles
A polygonalization of a set of points in the plane is a non-self-crossing polygon using all the points as vertices. One way to prove that it always exists is to observe that the traveling salesperson tour is always a polygonalization, because any two crossed edges can be uncrossed in two different ways, one of which preserves the connectivity of the tour, and this cannot increase the tour length. So if minimizing tour length eliminates all crossings, surely maximizing tour length must introduce as many crossings as possible, right?
-
Congratulations, Dr. Lunel!
Today I participated remotely in the successful doctoral defense of Corentin Lunel, who has been working in algorithmic low-dimensional topology with Arnaud de Mesmay and Pierre Dehornoy at the Laboratoire d’Informatique Gaspard Monge of Université Gustave Eiffel.
-
Linkage
- The Pentium as a Navajo weaving (\(\mathbb{M}\)), a 1994 rug by Marilou Schultz in the the National Gallery of Art designed from an image of the Intel Pentium integrated circuit.
-
Linkage
- Congratulations to Rajeev Alur of the the University of Pennsylvania for winning the 2024 Knuth Prize (\(\mathbb{M}\)), “for his introduction of novel models of computation which provide the theoretical foundations for analysis, design, synthesis, and verification of computer systems”!
-
Flaps and flips
My recent talk at OSME mostly surveyed known material on the computational difficulties of origami folding problems, some of which I’ve already discussed here: the impossibility of finding closed-form formulas for the coordinates of folded polyhedra and the fine-grained complexity of flat folding. But it also included some new results, showing that it’s hard to get from one folded state to another by changing one fold at a time, in the following toy folding problem, which I call “flaps and flips”.
subscribe via RSS