Header menu link for other important links
X
Planar projections of graphs
, U. Maniyar
Published in Elsevier B.V.
2022
Volume: 319
   
Pages: 216 - 222
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 Kn has a representation in ⌈n/2+2⌉ dimensions and Km,n has a representation in ⌈min(m,n)+1⌉ dimensions. In 3 dimensions, we show that there exist graphs with 6n−15 edges that can be projected onto two orthogonal planes, and that this is best possible. Finally, we obtain bounds in terms of geometric thickness and caterpillar arboricity, and show connections with unleveled planar graphs. Using such a bound, we show that every graph of maximum degree 5 has a plane-projectable representation in 3 dimensions. © 2021 Elsevier B.V.
About the journal
JournalData powered by TypesetDiscrete Applied Mathematics
PublisherData powered by TypesetElsevier B.V.
ISSN0166218X