-
Linkage
- A crowdsourced project to link erdosproblems.com with OEIS (\(\mathbb{M}\), see also), launched by Thomas Bloom and Terry Tao.
-
Planarizing matchings
The drawing below shows the Petersen graph (blue vertices), with order-six dihedral symmetry rather than the order-10 symmetry that you’re probably more used to. Three edges are highlighted by shaded ovals surrounding them; these edges form a matching, a set of edges that don’t touch each other. If you contract these edges, you get a graph with seven vertices: the three ovals and the remaining four blue vertices. This seven-vertex graph is planar, because all of the Petersen graph’s crossings are hidden inside the ovals. It turns out that, whenever you can contract a matching to make the resulting graph planar, the graph you started out with (here, the Petersen graph) is a string graph. This means that we can draw a curve in the plane (called a string) for each vertex of \(G\), so that two strings intersect if and only if the corresponding vertices are adjacent. Strings are allowed to intersect any number of times, not just once.
-
The metro map metaphor for treewidth
Harry Beck’s 1931 map of the London Underground transit system has been justly heralded. It abstracted the messiness of above-ground geography into simple lines in restricted directions and made a complex system visually understandable. Since Beck’s breakthrough, metro maps around the world have followed similar styles.
-
Linkage
- 3d and layered QR codes (\(\mathbb{M}\)). The QR code spec only measures the darkness of image pixels near the centers of grid points, allowing a lot of freedom to use the rest for decorative purposes.
-
Five-arc fractal
Start with an arc of a circle, like the red-to-red semicircle below. Then recursively subdivide it, at each step replacing a single arc of angle \(\theta\) by a piecewise-circular curve of five congruent arcs of angle \(\theta/3\). Keep in place the endpoints of the replaced arc and the tangent directions there. Make four of the five replacement arcs bend the same way as the arc they replaced, but bend the middle arc the opposite way.
-
Enclosures that minimize the sum of area and perimeter
If you want to enclose a bounded subset of the plane with the shortest possible fence (the perimeter of your enclosure), use its convex hull. If you want to enclose it with the minimum possible total area, use the set itself. This might be disconnected, but it doesn’t make any difference to ask for the minimum-area connected enclosure: for well-behaved subsets you can connect the pieces with a spanning tree or Steiner tree with zero additional area.
-
Linkage from Toronto
Last time I did one of these posts I was in Montreal for the 3rd Joint SIAM/CAIMS Annual Meetings (AN) and its satellite conferences on geometric design (GD) and applied and computational discrete algorithms (ACDA). This time, I’m back in Canada for the Algorithms and Data Structures Symposium (WADS) and Canadian Conference on Computational Geometry (CCCG). Yes, only some of those acronyms make sense. Anyway:
-
Linkage from Montreal
- 3-colouring planar graphs (\(\mathbb{M}\)), new preprint by Dujmović, Morin, Norin, and Wood showing that one can assign three colors to the vertices of any \(n\)-vertex planar graph in such a way that each monochromatic component has \(O(n^{4/9})\) vertices, improving a previous \(O(n^{1/2})\) bound. The best lower bound known is \(\Omega(n^{1/3})\).
-
Twenty years of blogging
I made my first post to this blog twenty years ago, on July 20, 2005.
-
Linkage
- Dozens of the world’s most cited scientists stop falsely claiming to work in Saudi Arabia (\(\mathbb{M}\)). Perhaps relatedly, Clarivate has tightened its checks for fraudulent citation practices and removed a greatly expanded number of researchers from its highly cited researcher lists.
subscribe via RSS