-
Doubled planar drawings of doubled planar graphs
If you start with a planar graph, and make two copies of each vertex, you should be able to draw the result as two planar graphs, right? But it’s more complicated than just copying a drawing of your starting graph, because you get four copies of each edge, and you have to put them all somewhere.
-
First linkage of the new year
- MathSciNet on my “Counting polygon triangulations is hard” (\(\mathbb{M}\)) says: “Of course, every \(\mathsf{NP}\)-complete problem gives rise to a \(\#\mathsf{P}\)-hard problem”. I assume it means: the counting problem for a witness-checker for an \(\mathsf{NP}\)-complete problem must be \(\#\mathsf{P}\)-hard. But is it true? The Berman–Hartmanis conjecture and Mahaney’s theorem seem relevant. Goldreich is more careful: “many counting problems associated with \(\mathsf{NP}\)-complete search problems are \(\#\mathsf{P}\)-complete”.
-
Year-end linkage
-
Tree-clique products
A tree decomposition of a graph is, intuitively, a representation of the graph as a “thickened” tree. It comes from the use of separators in divide-and-conquer algorithms: if a graph can be separated into two smaller subgraphs by the removal of a separator, a small subset of its vertices, then many algorithmic problems can be solved by a recursive algorithm that combines the solutions from those subgraphs. The tree, in the tree decomposition, has a root node that represents the separator at the top level of the recursion, children that represent the separators at the next level, and so on.
-
Linkage for the end of the Fall term
- This week’s hype (\(\mathbb{M}\), more, still more, even more, one more). And that’s just the Not Even Wrong posts; see them for a more thorough link and media roundup. Short summary: physicists ran a simulation of a quantum physics model that is unrelated to the conventional notion of wormholes from general relativity, sharing only a name with it. They used a quantum computer for the simulation even though it could as well have been run on a classical computer. And then they screamed from the rooftops that they had created the world’s first wormhole, apparently deliberately misleading everyone who didn’t read the fine print (including many major media outlets and research administrators) into thinking that they had brought into existence a physical wormhole.
-
Randomly traceable graphs
In my recently-concluded graph algorithms course, one of my early homework assignments asked about undirected graphs with the following property: any oriented path that does not cover all vertices can be extended to form a Hamiltonian path. I phrased it in terms of depth-first search: which graphs have the property that, no matter where you start and no matter what order you explore the neighbors of each node, a depth first search tree will automatically produce a Hamiltonian path? The intent was to reinforce the idea that the same graph can have multiple depth first search trees depending on contingent issues of how the graph is represented. I called these “unicursal graphs”.
-
Linkage
- Digital astronomy with cellular automata (\(\mathbb{M}\), via). No, this is not about using CA to study patterns in the sky (though that might be interesting); it is about using UMAP dimension-reduction techniques to create something like a Hertzsprung-Russell diagram for finding CA rules with complex behavior.
-
A straight line through every face
While updating my online publications list for something else I noticed that I had neglected to discuss one of my papers from earlier this fall: “Geodesic paths passing through all faces on a polyhedron” (with Demaine, Demaine, Ito, Katayama, Maruyama, and Uno), in the booklet of abstracts from JCDCG3 2022, the Japanese Conference on Discrete and Computational Geometry, Graphs, and Games.
-
Linkage
The massive influx of new users and new content to Mastodon has caused a greater number of these to be boosts of someone else’s post rather than posts of my own.
-
Report from LATIN
I just returned from the 15th Latin American Symposium on Theoretical Informatics (LATIN 2022), held this year in Guanajuato, Mexico. LATIN is a regional conference that is only offered every two years, like WADS in Canada and SWAT in Scandinavia. I had a paper in the first one, in 1992, but this is only the second one I’ve attended, after 2016 in Ensenada. This time, I was one of four invited speakers, speaking about reversible computing. My talk slides are online, and I think that a talk video should be uploaded by the conference in a week or so.
subscribe via RSS