Planar Projections of Graphs

Aravind, N. R. and Maniyar, Udit (2020) Planar Projections of Graphs. In: 6th International Conference on Algorithms and Discrete Applied Mathematics, CALDAM 2020, 13-15 February 2020, Hyderabad.

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 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.

[error in script]
IITH Creators:
IITH CreatorsORCiD
Aravind, N R
Item Type: Conference or Workshop Item (Paper)
Uncontrolled Keywords: Complete graphs; Graph drawing; Graph representation; Orthogonal plane; Parallel planes; Planar projection; Planarity; Thickness
Subjects: Computer science
Computer science > Algorithm Analysis
Divisions: Department of Computer Science & Engineering
Depositing User: . LibTrainee 2021
Date Deposited: 30 Jul 2021 04:21
Last Modified: 15 Nov 2022 12:08
Publisher URL:
OA policy:
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 8570 Statistics for this ePrint Item