Planar projections of graphs

Aravind, N R and Maniyar, Udit (2022) Planar projections of graphs. Discrete Applied Mathematics, 319. pp. 216-222. ISSN 0166-218X

Full text not available from this repository. (Request a copy)


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.

[error in script]
IITH Creators:
IITH CreatorsORCiD
Aravind, N R
Item Type: Article
Uncontrolled Keywords: Graph drawing; Planar projections; Planarity; Thickness
Subjects: Computer science
Divisions: Department of Computer Science & Engineering
Depositing User: . LibTrainee 2021
Date Deposited: 13 Sep 2022 09:38
Last Modified: 13 Sep 2022 09:38
Publisher URL:
OA policy:
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 10562 Statistics for this ePrint Item