I just returned from the 31st International Symposium on Graph Drawing and Network Visualization (GD ‘23), held this time in Isola delle Femmine, a small beach town on Sicily near Palermo. Despite the name it is not a separate island; the actual Isola delle Femmine is not the town, but a small barren island about a half kilometer offshore, decorated only by a ruined tower. Several conference participants (not me) swam to the island, several others were turned back by choppy water, and at least two were stung by jellyfish. Other than visiting the hotel beach I didn’t have much of a chance for sightseeing (the weather did not cooperate for the only large block of free time that I had) but I did enjoy the excellent Sicilian food and wine.

This was my first in-person GD since Barcelona in 2018 and it was good to be back and see old friends. One thing that was very noticeable was a strong level of participation by younger participants, and (unlike the old guard) a healthy gender balance among the younger participants. I think this speaks well to the continuing strength of this research community. There were, naturally, many Italians present, but also many Austrians and Germans, and smaller numbers of others scattered among other countries.

I would have thought the speakers on the last day had the advantage in the audience-voted best presentation award, as the freshest in voters’ minds. But the award went to one of the first-day speakers, Julia Katheder, for her paper “Weakly and strongly fan-planar graphs” (arXiv:2308.08966, with Cheong, Förster, Pfister, and Schlipf) clearing up the past literature on this class of graphs (defined through restrictions on their crossings) in light of the recent discovery that a previous forbidden-subdrawing characterization of them, used in several previous works, was incomplete. I think she sealed the victory by using an actual fan as a prop in her talk, but even without that she was a deserving winner. The two best papers were mine on biplanarity of blowups, in the theory track, and “CelticGraph: drawing graphs as Celtic knots and links” (arXiv:2309.02852, Eades, Gröne, Klein, Eades, Schreiber, Hailer, and Schreiber, with two father-son pairs).

A few other highlights for me from the first day included:

  • Niloufar Fuladi spoke on connections between the crossing number of planar drawings, uncrossed embeddings of graphs on higher-genus surfaces, and the signed pancake-flipping problem from genomics and Bill Gates fame (“Degenerate crossing number and signed reversal distance”, arXiv:2308.10666, with Hubard and de Mesmay).

  • Patricia Bachmann clarified that an old claim of a polynomial time algorithm for 3-coloring circle graphs (or finding 3-page book embeddings of ordered graphs) is certainly wrong (“On the 3-coloring of circle graphs”, arXiv:2309.02258, with Rutter and Stumpf). The complexity of this problem remains open.

  • Paul Jungeblut proved that it is complete for the existential theory of the reals to determine whether a graph has a Lombardi drawing (circular arc edges meeting at equal angles at each vertex): “On the complexity of Lombardi graph drawing”, arXiv:2306.02649).

The second day’s events included an invited talk by Monique Teillaud on the CGAL open-source computational geometry library, the conference business meeting, and a group dinner. At the business meeting we learned that next year’s conference will be in Vienna, with the proceedings publication switching from Springer LNCS to open access on LIPIcs. The proceedings has traditionally appeared several months after the conference, in part to allow the inclusion of a report from the graph drawing contest, and in part because of the lead time between submission of final versions and the proceedings publication; this seems likely to remain true after the changeover. In recent years we have also maintained a pseudo-proceedings on arXiv, so that papers would be available open access (getting open access through LNCS is far too expensive), but this also provided conference participants with timely access to the papers. A discussion ensued over whether we needed to continue to do this. It was left up to the PC chairs and steering committee, but one likely compromise would be to provide participants with the full final versions collected by the PC chair for the LIPIcs proceedings.

For me, the second-day highlights included:

  • András Sebő spoke on boxicity, the minimum dimension for which a graph can be represented as an intersection graph of hyper-rectangles: “Boxicity and interval-orders: Petersen and the complements of line graphs” (arXiv:2309.02062, with Caoduro). Sebő is new to graph drawing, usually working in combinatorial optimization, approximation, packing, and polyhedral combinatorics; I hope he found the community as welcoming as I have usually found it to be.

  • Pavel Valtr enlivened his talk (“Three edge-disjoint plane spanning paths in a point set”, arXiv:2306.07237, with Kindermann, Kratochvil, and Liotta) by presenting part of it on a T-shirt, sadly available only to the paper’s coauthors.

  • If I remember correctly, the presenter of “Cops and robbers on 1-planar graphs” (arXiv:2309.01001, Durocher, Kamali, Kryven, Liu, Mashghdoust, Miller, Zamani Nezhad, Penha Costa, and Zapp) was Myroslav Kryven. The paper proves that three cops can catch a robber on some graphs drawn with at most one crossing per edge, when each player can either stay put or move along one edge per turn. More precisely, maximal 1-planar graphs have cop number at most three.

The final day of the main conference included another invited talk, by Michael Kaufmann on orthogonal drawing, and the award presentations. As well as the ones I already mentioned, there was an audience-voted best-poster contest, won by “What happens in Dagstuhl…” (Klesen, Miller, Montecchiani, Nöllenburg, and Wallinger), a visualization of interactions at this workshop center. My personal favorite was “A collection of benchmark datasets for evaluating graph layout algorithms” (Di Bartolomeo, Puerta, Wilson, Cronvrsanin, and Dunne). Unfortunately it does not seem to be possible to find the posters online, but the benchmarks themselves are on the Open Science Framework. Highlight talks for me included:

  • The entire first session concerned parameterized complexity, including papers on bend-minimal orthogonal planar drawing (arXiv:2308.13665), right-angle-crossing (RAC) drawings (arXiv:2308.10600), simultaneous embedding (2308.11401, and drawing graphs so that the edges line up into a small number of line segments (arXiv:2308.15416). I didn’t notice until after the conference that one of the coauthors on the last of these (not present at the conference) is my former student Sid Gupta.

  • A standard tool in graph drawing is the Schnyder wood, a covering of any 3-connected planar triangulation by three forests. It can alternatively be described by a constrained labeling of corners of the triangles by the numbers 1, 2, and 3, in clockwise order, with the labels appearing in contiguous blocks at each vertex. Éric Fusy spoke about generalizations to 4 trees and 4 labels in 4-connected graphs and to 5 trees and 5 labels in 5-connected graphs (“A Schnyder-type drawing algorithm for 5-connected triangulations”, arXiv:2305.19058, with Bernardi and Liang).

  • Tim Hegemann’s talk (“A simple pipeline for orthogonal graph drawing”, arXiv:2309.01671, with Wolff) was notable to me not so much for its methods, but for the application he presented: a farm machinery company builds large harvesters that each include a unique combination of components. When these machines need repair, the technicians use functional diagrams of these components, depicted with boxes for the components and axis-parallel polylines for their connections. So they need a way of producing large numbers of readable diagrams, automatically.

That wasn’t the end of the gathering, though, because there was a final day for “BeppeFest”, an elaborate celebration of Beppe Liotta’s 60th birthday, featuring two sessions of invited talks by Beppe’s old friends overviewing their joint research, and another dinner including an elaborate show of musical pastiches (several involving the talented Alessandra Tappini), quiz questions for Beppe about past conferences, and congratulatory videos. Happy birthday, again, Beppe!

(Discuss on Mastodon)