Premium
Graphs embedded in the plane with a bounded number of accumulation points
Author(s) -
Bonnington C. Paul,
Richter R. Bruce
Publication year - 2003
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.10133
Subject(s) - mathematics , combinatorics , embedding , bounded function , planar graph , vertex (graph theory) , discrete mathematics , 1 planar graph , plane (geometry) , characterization (materials science) , chordal graph , graph , geometry , mathematical analysis , computer science , materials science , artificial intelligence , nanotechnology
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 ℤ 2 ‐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 Thomassens's result, obtaining a cycle space characterization of a graph having an embedding in the sphere with k accumulation points. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 132–147, 2003