𝔖 Bobbio Scriptorium
✦   LIBER   ✦

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

✍ Scribed by C. Paul Bonnington; R. Bruce Richter

Publisher
John Wiley and Sons
Year
2003
Tongue
English
Weight
138 KB
Volume
44
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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 β„€~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

πŸ“œ SIMILAR VOLUMES

A general upper bound for the cyclic chr
A general upper bound for the cyclic chromatic number of 3-connected plane graphs
✍ Hikoe Enomoto; Mirko HorňÑk πŸ“‚ Article πŸ“… 2009 πŸ› John Wiley and Sons 🌐 English βš– 457 KB πŸ‘ 1 views

## Abstract The cyclic chromatic number of a plane graph __G__ is the smallest number Ο‡~__c__~(__G__) of colors that can be assigned to vertices of __G__ in such a way that whenever two distinct vertices are incident with a common face, they receive distinct colors. It was conjectured by Plummer an

On the Density of Subgraphs in a Graph w
On the Density of Subgraphs in a Graph with Bounded Independence Number
✍ Pavel Valtr πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 260 KB

Let \_(n, m, k) be the largest number \_ # [0, 1] such that any graph on n vertices with independence number at most m has a subgraph on k vertices with at lest \_ } ( k 2 ) edges. Up to a constant multiplicative factor, we determine \_(n, m, k) for all n, m, k. For log n m=k n, our result gives \_(

On the Number of Acute Triangles in a St
On the Number of Acute Triangles in a Straight-Line Embedding of a Maximal Planar Graph
✍ Atsushi Kaneko; Hiroshi Maehara; Mamoru Watanabe πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 80 KB

In this paper we show that any maximal planar graph with m triangles except the unbounded face can be transformed into a straight-line embedding in which at least WmΓ‚3X triangles are acute triangles. Moreover, we show that any maximal outerplanar graph can be transformed into a straight-line embeddi