Infinite families of crossingcritical 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, kcrossingcritical graphs) (J. Combin. Theory Ser. B 58 (2) (1993) 217224) Richter and Thomassen described a construction of an infinite family of 4regular 3crossingcritical graphs. They also showed that no infinite family of 6regular kcrossingcritical 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 kcrossingcritical 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; Crossingcritical; 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