On Fri, 22 Mar 2013 23:52:17 -0700 (PDT), Butch Malahide <email@example.com> wrote:
>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.
I think that's right, maybe.
>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.
Right. Whether you got every detail right here (which is not so say you didn't, just that I haven't thought about it carefully), it's clear that this or something like this does give a way to enumerate those compactifications by testing graphs for isomorphism. Thanks.