Donald Knuth’s Annual Christmas Tree Lecture: Planar Graphs and Ternary Trees
From the description:
In this lecture, Professor Knuth discusses the beautiful connections between certain trees with three-way branching and graphs that can be drawn in the plane without crossing edges.
Additional resources that will be helpful:
From Knuth’s Programs to Read:
SKEW-TERNARY-CALC and a MetaPost file for its illustrations.
Computes planar graphs that correspond to ternary trees in an amazing way; here’s a PDF file for its documentation
Quad-edge (Wikipedia)
Quad-Edge Data Structure and Library by Paul Heckbert.
The Quad-Edge data structure is useful for describing the topology and geometry of polyhedra. We will use it when implementing subdivision surfaces (a recent, elegant way to define curved surfaces) because it is elegant and it can answer adjacency queries efficiently. In this document we describe the data structure and a C++ implementation of it.
I don’t think this will be immediately applicable to topic maps because planar graphs are embedded in a plane (or on a sphere) and their edges only intersect at nodes.
Thinking that scope requires the use a hyperedge. Yes?
However, the lecture is quite enjoyable and efficient data structures may inspire thoughts of new efficient data structures.