New Relations between Thickness and Outer Thickness of a Graph and its Arboricity
B. Nikfarjam, M. Yunusi · 2011
The thickness of a graph is the minimum number of planar into which the graph can be decomposed. Determining the thickness of a graph is known too NP-complete problem. The outer thickness of a graph is minimum number of outer planar into which the graph can be decomposed. Outer thickness is one of the classical and standard measures of non-outer planarity of graphs. We conjecture that determining the outer thickness of a graph is also NP-complete. Arboricity of a graph is the minimum number of edge-disjoint forests whose union is G. In this paper, we show the new relations between thickness and outer thickness of a graph and its arboricity.