-
Hamiltonian-paired graphs
The five-vertex complete graph \(K_5\) is commonly drawn with its vertices on a regular polygon. In this layout, it is easy to find two Hamiltonian cycles that are complementary to each other, forming a Hamiltonian decomposition: the outer pentagon and the inner pentagram. In fact in this graph every Hamiltonian cycle is complementary to another one: the complement graph must be 2-regular (because a Hamiltonian cycle uses exactly two of the four edges at each vertex, leaving another two) and the only two-regular graph on five vertices is a cycle.
-
Linkage
-
Linkage with feijoas
- The season’s first feijoas (aka pineapple guavas) fell from the trees in my front garden (that’s how to tell they are ripe). They are the ones in the bowl on the right; other fruit included for scale (\(\mathbb{M}\)).
-
Norrköpingsfallen
I just returned from the International Symposium on Graph Drawing and Network Visualization, held this year in Norrköping, Sweden. Norrköping was an early paper and textile milling town, set at the mouth of the Motala ström, a river that flows into the Baltic Sea. At this point of the river, a cascade of three waterfalls, Norrköpingsfallen, provided power for the mills. The old industrial buildings surrounding the falls have largely survived but been turned to other uses. The conference was held in the Louis de Geer Concert & Congress, at the lowest and biggest of these falls. Despite having long since been dammed and tamed, it was still spectacular.
-
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.
subscribe via RSS