TY - JOUR
T1 - Separating double rays in locally finite planar graphs
AU - Paul Bonnington, C.
AU - Imrich, Wilfried
AU - Watkins, Mark E.
PY - 1995/10/13
Y1 - 1995/10/13
N2 - The main aim of this paper is to characterize infinite, locally finite, planar, 1-ended graphs by means of path separation properties. Let Γ be an infinite graph, let Π be a double ray in Γ, and let d and dΠ denote the distance functions in Γ and in Π, respectively. One calls Π a quasi-axis if lim inf d(x, y)/dΠ(x, y) > 0, where x and y are vertices of Π and dΠ(x, y) → ∞. An infinite, locally finite, almost 4-connected, almost-transitive, 1-ended graph is shown to be planar if and only if the complement of every quasi-axis has exactly two infinite components. Let Γ be locally finite, planar, 3-connected, almost-transitive, and 1-ended. It is shown that no proper planar embedding of Γ has an infinite face and hence its covalences are bounded. If Γ has bounded covalences and if Π is any double ray in Γ, it is shown that Γ - Π has at most two infinite components, at most one on each side of Π. If, moreover, Π is a quasi-axis, then Γ - Π is shown to have exactly two infinite components. With the aid of a result of Thomassen (1992), the above-stated characterization of infinite, locally finite, planar, 1-ended graphs is then obtained.
AB - The main aim of this paper is to characterize infinite, locally finite, planar, 1-ended graphs by means of path separation properties. Let Γ be an infinite graph, let Π be a double ray in Γ, and let d and dΠ denote the distance functions in Γ and in Π, respectively. One calls Π a quasi-axis if lim inf d(x, y)/dΠ(x, y) > 0, where x and y are vertices of Π and dΠ(x, y) → ∞. An infinite, locally finite, almost 4-connected, almost-transitive, 1-ended graph is shown to be planar if and only if the complement of every quasi-axis has exactly two infinite components. Let Γ be locally finite, planar, 3-connected, almost-transitive, and 1-ended. It is shown that no proper planar embedding of Γ has an infinite face and hence its covalences are bounded. If Γ has bounded covalences and if Π is any double ray in Γ, it is shown that Γ - Π has at most two infinite components, at most one on each side of Π. If, moreover, Π is a quasi-axis, then Γ - Π is shown to have exactly two infinite components. With the aid of a result of Thomassen (1992), the above-stated characterization of infinite, locally finite, planar, 1-ended graphs is then obtained.
UR - http://www.scopus.com/inward/record.url?scp=58149323460&partnerID=8YFLogxK
U2 - 10.1016/0012-365X(94)00054-M
DO - 10.1016/0012-365X(94)00054-M
M3 - Article
AN - SCOPUS:58149323460
SN - 0012-365X
VL - 145.1995
SP - 61
EP - 72
JO - Discrete mathematics
JF - Discrete mathematics
IS - 1-3
ER -