Infinite families of crossing-critical graphs with given average degree
Article
-
- Overview
-
- Research
-
- Identity
-
- Additional Document Info
-
- View All
-
Overview
abstract
-
In their paper on minimal graphs with crossing number at least k (or, equivalently, k-crossing-critical graphs) (J. Combin. Theory Ser. B 58 (2) (1993) 217-224) Richter and Thomassen described a construction of an infinite family of 4-regular 3-crossing-critical graphs. They also showed that no infinite family of 6-regular k-crossing-critical graphs exists. In this paper we generalize the Richter and Thomassen construction, and prove the following result: for each rational number q[4,6) there is an infinite family of graphs that are k-crossing-critical for the same integer k, each of which has average degree q. Moreover, we show that for each rational number q[4,6) this statement holds for infinitely many values of k. © 2003 Elsevier B.V. All rights reserved.
publication date
published in
Research
keywords
-
Crossing number; Crossing-critical; Graph drawing Drawing (graphics); Integer programming; Theorem proving; Crossing number; Graph theory
Identity
Digital Object Identifier (DOI)
Additional Document Info
start page
end page
volume
issue