Report from JCDCG³
I suppose I should write down my recollections of JCDCG^{3} before they fade too badly. It was only my second conference in Japan, and the first one was nearly 20 years earlier (PARAOPT V, at the invitation I think of Naoki Katoh). This time, the invitation was by Hiro Ito, but unfortunately he fell ill and couldn’t attend. Instead, the position of host was capably handled by Jin Akiyama. Here are Jin and Naoki with me and my wife Diana, photographed by Toshinori Sakai (who despite being behind the lens for most of the conference, mysteriously appears in many past conference photos):
This was the 20th anniversary of the conference, and was dedicated in celebration of five of its regular contributors: Jin Akiyama, Vašek Chvátal, Mikio Kano, János Pach, and Jorge Urrutia. Along with those five, there were four more invited plenary speakers (Erik Demaine, Naoki Katoh, Evangelos Kranakis, and myself), and four days of doublesession contributed talks. There’s a 15Mb pdf collection of abstracts online, but the booklet they handed out at the conference was, instead, a 75page illustrated history of the conference (which doesn’t seem to be online). As usual the full proceedings will be published later.
I attended most of the conference (missing one early morning session) but that still means I saw fewer than half of the contributed talks. Some of the highlights for me:

I thought almost everything was known about how many guards are needed in most natural variants of the art gallery problem. But in the opening invited talk, Jorge Urrutia mentioned an open problem that was new to me: suppose you want to guard a simple orthogonal polyhedron by as few edge guards as possible. That is, you need to choose as few edges of the polyhedron as possible so that every point of the polygon is visible from one of the edges through the polyhedron interior. One way to do this is to consider the crosssections parallel to one of the three coordinate planes (orthogonal polygons). From any point within any crosssection, look north, then sweep your gaze clockwise; you will either run into the east end of a southfacing wall or the north end of a westfacing wall. That is, the set of east ends of south walls and north ends of west walls is unavoidable; every point is visible from one such corner. In the same way you can find three other unavoidable sets of corners, such that each corner of the crosssection belongs to two of the four unavoidable sets. Doing the same thing for the two other coordinate planes generates a total of 12 unavoidable sets of edges of the polyhedron, with each edge belonging to two sets, so one of them gives a guard set with at most \(E/6\) guards where \(E\) is the total number of edges. Very recently, Urrutia has managed to improve this slightly, to \(11E/72.\) But the only known lower bound is \(E/12O(1),\) from a big cube with many small cubical bumps on one of its faces, so there’s still a big gap to close.

In my own talk on forbidden configurations, I asked whether Erdős and Szekeres knew about the lower bound for the happy ending problem when they conjectured the formula for the problem in 1935, or not until they actually published the lower bound in 1960. I got conflicting responses: Pach told me he asked them this question, and that the conjecture was purely youthful optimism after seeing the numbers of points needed to force a triangle, quadrilateral, or pentagon. But Chvátal told me instead that Szekeres wrote (perhaps in the 60thbirthday festschrift for Erdős) that they knew the lower bound but held off on publishing it because they thought it was too easy. So I still don’t know.

Min Yan provided some interesting ways of transforming any tiling of the plane or a sphere into a subdivided pentagonal tiling, on the way to classifying all tilings of the sphere by congruent pentagons. They’re probably easier to draw than to describe in text; the thick black edges below show the existing tiling and the thin colored edges show the new edges added in the subdivision.

Lowdimensional topologist Genevieve Walsh, slumming as a discrete geometer, asked which topological triangulations of the sphere can be realized by acute triangles. The answer in the plane was known by Maehara in 2003, who showed that a disk can be acutely triangulated by a given triangulation if and only if no triangle or quadrilateral encloses a point. Walsh’s new theorem is that on the sphere, a triangulation can be made acute if and only if no triangle or quadrilateral has points on both of its sides. The proof involves the circle packing theorem and an equivalence between acute sphere triangulations and hyperbolic convex polyhedra with right dihedrals.

János Pach’s talk concerned the crossing lemma, that a drawing of a graph with \(n\) vertices and \(m\ge 4n\) edges has \(\Omega(m^3/n^2)\) crossings, and its extension to hypergraphs. In the hypergraph case one can’t just take the input as an abstract graph, because there are hypergraphs with many edges and no crossings (for instance repeat many edges of a planar graph) but instead one should consider “simple topological multigraphs”, multigraphs drawn with at most one crossing per edge pair, no crossings of incident edges, and no empty digons. The usual probabilistic proof of the crossing lemma (take a random sample of the edges small enough to reduce the number of edges to \(4n\), and compare the expected number of crossings from the sample with the fact that you still have at least a linear number of crossings) doesn’t work, because random sampling can destroy the noemptydigon property. Instead he proves the multigraph version of the lemma by a connection between crossing number and bisection width (somewhat related to my new GD paper on width?) that he had proved with Shahrokhi and Szegedy in 1996:

It is known that you can collapse a (hollow) cube down onto one of its square faces, keeping that face and the opposite face flat and parallel, and folding the four faces between them. However to do so you have to use a “rolling fold”, one whose position on a folded face continuously shifts; it’s not possible to do this as rigid origami. Chie Nara spoke on a higher dimensional generalization: you can fold a hypercube onto one of its square faces, keeping the opposite face parallel to it. Again, she used rolling folds, but Tomohiro Tachi asked whether the extra flexibility of the higher dimensions might allow that to be avoided. (Nara didn’t know, and I don’t either.) The next talk also involved Nara, flattening, and an interesting class of 3d polyhedra that I hadn’t previously seen: “semiorthogonal polyhedra”, the polyhedra in which all faces are either parallel to or perpendicular to a common line.

Elena Khramtcova started her talk by handing out paper regularhexagons and tape, and asked us to fold and tape the hexagons to form a convex polyhedron. For instance, it’s not hard to make a regular octahedron this way, or an (irregular) triangular prism; see the nets and gluing patterns below. Three hexagons glue together to form a flat piece of paper, so the vertices of the polyhedra must be missing either one or two of those three hexagons, with six missing altogether. It was distracting enough that I don’t remember exactly what results she presented, but they were a partial classification of the combinatorial types of shapes you can form, with some cases still open. Soon after, Jason Ku solved one of the open cases: a rectangular pyramid with a sharp angle (two missing hexes) at its apex and blunter angles (one missing hex) at the other four vertices. I’ll leave its solution as a puzzle for readers.

Naoki Katoh spoke about how to make square grids rigid by adding diagonal crossbraces. He started with a small brain teaser: if you crossbrace the four corner squares of a \(3\times 3\) grid, is the result rigid? If you think of these braces as edges in a bipartite graph, whose vertices are rows and columns of squares in the grid, then a minimally rigid set of braces corresponds to a spanning tree in the graph. That is, the rigidity matroid for this case is a graphic matroid. But the problem becomes more complicated when the square grid can have holes in it rather than forming a simplyconnected polyomino. Again, he provided an activity to involve the audience: a game involving a mechanical grid of squares, with a set number of crossbraces. Two players alternate in placing the crossbraces, with one trying to make the structure rigid and the other trying to keep it flexible. With a minimal number of crossbraces and a large grid, this is too easy for the flexible player to win (just place four braces making a 4cycle in the underlying bipartite graph, ignoring what the other player does) but there should be some larger number of braces that makes it more of an even struggle.

Aaron Williams offered a similar distraction for his talk: he handed out Arduboys loaded with his implementation of MazezaM while he talked about his proof that puzzle solutions can be exponentially long (a step towards \(\mathsf{PSPACE}\)completeness). The puzzle is polynomial for a fixed number of rows (because the number of states is \(\mathrm{cols}^{\mathrm{rows}}\)) raising the question of its parameterized complexity. I didn’t get very far with the Arduboy because I wanted to pay some attention to the actual talk. Somewhere out there is a photo of several of us showing off the Arduboys.

Rudolf Fleischer studied some problems involving what happens when you repeatedly do perfect shuffles of a card deck, but change whether you use inshuffles or outshuffles. For deck sizes of size a power of two, these shuffles can be described (in terms of their action on the indexes of the cards) as either a binary rotation, or a rotation followed by flipping the loworder bit. The Cayley graph of these operations is a directed graph resembling, but not quite the same as, the cubeconnected cycles, the Cayley graph of the action on binary words by rotations and loworder flips (as separate operations). I wonder what is known about the structure of these graphs.

Several of the invited talks were historical reminiscences rather than technical, but Mikio Kano found time to tell us about some problems related to the ham sandwich theorem, involving line partitions of a tricolored set of points with no majority color into subsets with the same nomaj property, a problem Sakai also spoke about in a contributed talk. Together they showed that when the number of points is a multiple of four, one can find a partition of this type in which each side is still a multiple of four, allowing a recursive partition of the plane into convex regions with only four points each, no three the same color. However a counterexample from Jan Kynčl shows that it’s not always possible to evenly trisect large multipleofsix nomaj point sets by a convex partition.

Jin Akiyama gave another intalk demonstration, asking us to cut paper envelopes by two trees, one on each side, spanning the four envelope corners. If you cut only one tree, you get a shape that tiles the plane. If you cut both trees, you get four shapes that can be reassembled in two different ways, to form either of the two tiles generated by one of the two trees. By combining the same trees in different pairs on different envelopes, one can get a sequence of dissections from one shape into another, which he showed off over the course of a story about his life: not being able to decide between mathematics and sailing, he goes fishing and catches a fish with shrimp as bait (shrimp turns into fish), but a cat steals the fish (fish turns into cat), the cat chokes and its body is made into a shamisen (cat turns into shamisen), and he sells the shamisen to a geisha (shamisen turns into geisha), who wisely advises him to use the money to go to the university and study hard (geisha turns into university).

Hiroshi Nishiyama spoke on odddepth trees: rooted spanning trees of a given rooted graph in which all leaves have odd distance from the root. (The root does not count as a leaf, even if it has degree one.) In bipartite graphs it can be solved by matroid intersection: find the largest forest (one matroid) in which every vertex other than the root on the same side of the bipartition has at most two neighbors (the other matroid). If it provides exactly two neighbors to all the rootside vertices, you can extend it to an odddepth tree, and otherwise no. But for biconnected nonbipartite graphs it’s \(\mathsf{NP}\)complete.

Masanori Fukui, Koki Suetsugu, and Akira Suzuki contributed a paper on Goishi Hiroi, a Hamiltonianpathlike puzzle from a 1727 Japanese puzzle book. Given a collection of stones on a grid you need to find a path of axisaligned segments that visits all the stones. The path can jump over empty spaces or stones that are already on the path but not other stones, and can’t make any Uturns. They show that it’s \(\mathsf{NP}\)complete, but the reduction involves unrealistic problem setups with disconnected islands of stones. It’s still open how hard it is when the initial set of stones forms a single contiguous group.

Yasuaki Kobayashi, Koki Suetsugu, and Hideki Tsuiki contributed another paper on a family of puzzles with the intriguing property that they’re \(\mathsf{GI}\)complete rather than having a higher or lower complexity. They’re called “lattice puzzles” (here is an example) and they consist of a collection of metal or plastic strips, with slots of different heights that allow one strip to connect to another perpendicular strip. The goal is to connect all of the strips in this way to form a square lattice of strips. If you start out knowing which strips are horizontal and which vertical, then you can think of it as finding a permutation of the horizontal strips that causes their slots to match up with the slots in another permutation of the vertical strips. And if the slots have only two heights then this turns out to be exactly the problem of finding an isomorphism between a bipartite graph determined from the slots of one height on the horizontal strips and another bipartite graph determined from the complementary height on the vertical strips.
Overall, quite a fun conference. I hope it doesn’t take me quite so long to return next time!