Graphs Embedded in the Plane with Finitely Many Accumulation Points

Abstract

Halin's Theorem characterizes those infinite connected graphs that have an embedding in the plane with no accumulation points, by exhibiting the list of excluded subgraphs. We generalize this by obtaining a similar characterization of which infinite connected graphs have an embedding in the plane (and other surfaces) with at most k accumulation points. Thomassen [7] provided a different characterization of those infinite connected graphs that have an embedding in the plane with no accumulation points as those for which the bfZ2-vector space generated by the cycles has a basis for which every edge is in at most two members. Adopting the definition that the cycle space is the set of all edge-sets of subgraphs in which every vertex has even degree (and allowing restricted infinite sums), we prove a general analogue of Thomassen's result, obtaining a cycle space characterization of a graph having an embedding in the sphere with k accumulation points.