Graphs embedded in the plane with a bounded number of accumulation points

Craig Paul Bonnington, R Bruce Richter

Research output: Contribution to journalArticleResearchpeer-review

11 Citations (Scopus)

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 Z2-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 Thomassena s result, obtaining a cycle space characterization of a graph having an embedding in the sphere with k accumulation points.
Original languageEnglish
Pages (from-to)132 - 147
Number of pages16
JournalJournal of Graph Theory
Volume44
Issue number2
DOIs
Publication statusPublished - 2003

Cite this