Header menu link for other important links
X
Planar Projections of Graphs
, U. Maniyar
Published in Springer
2020
Volume: 12016 LNCS
   
Pages: 453 - 462
Abstract
We introduce and study a new graph representation where vertices are embedded in three or more dimensions, and in which the edges are drawn on the projections onto the axis-parallel planes. We show that the complete graph on n vertices has a representation in \sqrt{n/2}+1 \rceil planes. In 3 dimensions, we show that there exist graphs with edges that can be projected onto two orthogonal planes, and that this is best possible. Finally, we obtain bounds in terms of parameters such as geometric thickness and linear arboricity. Using such a bound, we show that every graph of maximum degree 5 has a plane-projectable representation in 3 dimensions. © 2020, Springer Nature Switzerland AG.