On Mar 22, 10:27 pm, Butch Malahide <fred.gal...@gmail.com> wrote: > On Mar 22, 10:52 am, David C. Ullrich <ullr...@math.okstate.edu> > wrote: > > > > > > > I just realized I have no idea whatever how to write > > a correct algorithm here, even without worrying > > about efficiency. > > > An equivalence relation on the 2n endpoints > > determines a compactification. It also determines > > a graph, where the vertices are the equivalence > > classes of endpoints and the edges are the > > original segments. Earlier, thinking that I was > > thinking about deciding when two of these > > compactifications are homeomorphic, I was > > actually thinking about how to determine > > whether two of the graphs are isomorphic. > > That's a strictly weaker condition... I have > > no idea how I'd check whether two equivalences > > gave homeomorphic compactifications. > > You mean, non-isomorphic is a weaker condition than non-homeomorphic. > > The remedy for that is to stick to graphs with no vertices of degree > 2. (OK, you have to make an exception for the graph consisting of a > single vertex of degree 2, corresponding to the one-point > compactification of R.)
Oops, I was thinking of connected graphs. In general, you want to work with graphs with the property that any vertex of degree 2 is the only vertex in its component. OK, so you have graphs G and H that you want to test for homeomorphism. Remove vertices of degree 2 (and unify the two edges that were incident with that vertex) until you get graphs G' and H', homeomorphic to G and H respectively (G and H are subdivisions of G' and H') and having the aforesaid property; and then test G' and H' for isomorphism. So homeomorphism testing (of graphs) is no harder than isomorphism testing.