On the thickness of graphs of given degree (Q1174334): Difference between revisions

The results presented here refer to the determination of the thickness of a graph, that is, the minimum number of planar subgraphs into which the graph can be decomposed. Let \(D\) and \(T\) be positive integers, such that any graph of degree at most \(D\) has thickness at most \(T\). The author proves the following: (1) A planar graph has a planar representation for any arbitrary placement of its nodes in the plane. (2) Any graph of degree \(d\) has thickness at most \(T\lceil(d+2)/D\rceil\). (3) Any graph of degree \(d\) can always be embedded in a regular graph of any degree \(f\geq d\). (4) Any graph of degree \(d\) has thickness at most \(\lceil d/2\rceil\). (5) \(D\leq 4T-2\).