Home  Issues  About JGAA  Instructions for Authors 
Special Issue on Parameterized and Approximation Algorithms in Graph Drawing
DOI: 10.7155/jgaa.00630
The Complexity of Drawing Graphs on Few Lines and Few Planes
Steven Chaplick,
Krzysztof Fleszar,
Fabian Lipp,
Alexander Ravsky,
Oleg Verbitsky, and
Alexander Wolff
Vol. 27, no. 6, pp. 459488, 2023. Regular paper.
Abstract It is well known that any graph admits a crossingfree straightline
drawing in $\mathbb{R}^3$ and that any planar graph admits the same even
in $\mathbb{R}^2$. For a graph $G$ and $d \in \{2,3\}$, let
$\rho^1_d(G)$ denote the smallest number of lines in $\mathbb{R}^d$
whose union contains a crossingfree straightline drawing of $G$.
For $d=2$, the graph $G$ must be planar. Similarly, let
$\rho^2_3(G)$ denote the smallest number of planes
in $\mathbb{R}^3$ whose union contains a crossingfree straightline
drawing of $G$.
We investigate the complexity of computing these three parameters and obtain the following hardness and algorithmic results.
This work is licensed under the terms of the CCBY license.

Submitted: June 2022.
Reviewed: September 2022.
Revised: November 2022.
Reviewed: February 2023.
Revised: February 2023.
Reviewed: April 2023.
Accepted: April 2023.
Final: July 2023.
Published: July 2023.

Journal Supporters
