I have a new preprint on arXiv: Ramified Rectilinear Polygons: Coordinatization by Dendrons (with Hans-Jürgen Bandelt and Victor Chepoi; arXiv:1005.1721).

This is a study of the graphs that can be embedded in a distance-preserving way into the Cartesian products of two trees, and the cell complexes that one gets by filling in the quadrilaterals of such a graph by rectangles. The title refers to the fact that any orthogonal polygon can be formed in this way, leading to a system of coordinates in which the usual Cartesian $$x$$ and $$y$$ axis lines are replaced by trees; geodesic Manhattan distance within the polygon is just the sum of the coordinatewise distances.

A graph that is an isometric subgraph of the product of two trees must be a cube-free median graph, but in some ways these graphs are simpler than the class of all cube-free median graphs: for instance, they can be recognized in linear time using LexBFS, whereas recognition of cube-free median graphs is provably equivalent to testing for the existence of triangles in sparse graphs, a problem that is not known to be solvable more quickly than $$O(n^{1.41})$$

Why only two trees? Because the theory becomes very messy very quickly beyond that. In particular, $$k$$-coloring a graph is almost the same thing as embedding its simplex graph onto a product of $$k$$ trees, so it's NP-complete to tell whether a graph is an isometric subgraph of three trees.

justinwsmith:

None: Unrelated to anything, maybe
2010-08-05T03:43:32Z

Point P is inside a tetrahedron, so it has a line to each vertex. Those four lines determine 6 angles. I am trying to prove that of the six angles, at least three must be obtuse. I'm not asking for a proof but if you know where one is, I'd like to know. Thanks!