Ramified rectilinear polygons
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.
Comments:
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!
stevebg@roadrunner.com
2010-08-05T04:04:45Z
I assume by "inside" you mean strictly interior to the tetrahedron; otherwise, not all the angles are necessarily well defined.
Suppose that APB, APC, and APD were all non-obtuse. Then B, C, and D would all belong to a halfspace whose boundary passes through P, perpendicular to line AP. But then, because all the points belong to a halfspace, P would at best be on the boundary of the halfspace rather than interior to it. Therefore, at least one of the angles involving A must be obtuse. Same with the other four points. So this at least proves that there must be two obtuse angles (say APB and CPD). It looks likely that a similar argument involving looking at the angles of lines AC and AD with respect to plane APB finishes the proof.