It is well known that any graph admits a crossing-free straight-line drawing in \$\$\backslashmathbb \R\ ^3\$\$ and that any planar graph admits the same even in \$\$\backslashmathbb \R\ ^2\$\$ . For a graph G and \$\$d \backslashin \backslash\2,3\backslash\\$\$ , let \$\$\backslashrho ^1\_d(G)\$\$ denote the minimum number of lines in \$\$\backslashmathbb \R\ ^d\$\$ that together can cover all edges of a drawing of G. For \$\$d=2\$\$ , G must be planar. We investigate the complexity of computing these parameters and obtain the following hardness and algorithmic results.
Description
The Complexity of Drawing Graphs on Few Lines and Few Planes | SpringerLink
%0 Book Section
%1 Chaplick2017
%A Chaplick, Steven
%A Fleszar, Krzysztof
%A Lipp, Fabian
%A Ravsky, Alexander
%A Verbitsky, Oleg
%A Wolff, Alexander
%B Proc. Algorithms Data Struct. Symp. (WADS'17)
%C Cham
%D 2017
%E Ellen, Faith
%E Kolokolova, Antonina
%E Sack, Jörg-Rüdiger
%I Springer
%K conference myown publication
%P 265--276
%R 10.1007/978-3-319-62127-2_23
%T The Complexity of Drawing Graphs on Few Lines and Few Planes
%U https://doi.org/10.1007/978-3-319-62127-2_23
%X It is well known that any graph admits a crossing-free straight-line drawing in \$\$\backslashmathbb \R\ ^3\$\$ and that any planar graph admits the same even in \$\$\backslashmathbb \R\ ^2\$\$ . For a graph G and \$\$d \backslashin \backslash\2,3\backslash\\$\$ , let \$\$\backslashrho ^1\_d(G)\$\$ denote the minimum number of lines in \$\$\backslashmathbb \R\ ^d\$\$ that together can cover all edges of a drawing of G. For \$\$d=2\$\$ , G must be planar. We investigate the complexity of computing these parameters and obtain the following hardness and algorithmic results.
%@ 978-3-319-62127-2
@inbook{Chaplick2017,
abstract = {It is well known that any graph admits a crossing-free straight-line drawing in {\$}{\$}{\backslash}mathbb {\{}R{\}} ^3{\$}{\$} and that any planar graph admits the same even in {\$}{\$}{\backslash}mathbb {\{}R{\}} ^2{\$}{\$} . For a graph G and {\$}{\$}d {\backslash}in {\backslash}{\{}2,3{\backslash}{\}}{\$}{\$} , let {\$}{\$}{\backslash}rho ^1{\_}d(G){\$}{\$} denote the minimum number of lines in {\$}{\$}{\backslash}mathbb {\{}R{\}} ^d{\$}{\$} that together can cover all edges of a drawing of G. For {\$}{\$}d=2{\$}{\$} , G must be planar. We investigate the complexity of computing these parameters and obtain the following hardness and algorithmic results.},
added-at = {2017-09-13T10:07:36.000+0200},
address = {Cham},
author = {Chaplick, Steven and Fleszar, Krzysztof and Lipp, Fabian and Ravsky, Alexander and Verbitsky, Oleg and Wolff, Alexander},
biburl = {https://www.bibsonomy.org/bibtex/2ff926d86a024af6857988b10851a95f7/chaplick},
booktitle = {Proc. Algorithms Data Struct. Symp. (WADS'17)},
description = {The Complexity of Drawing Graphs on Few Lines and Few Planes | SpringerLink},
doi = {10.1007/978-3-319-62127-2_23},
editor = {Ellen, Faith and Kolokolova, Antonina and Sack, Jörg-Rüdiger},
interhash = {a60ddbaa74f4f93956bf779200355549},
intrahash = {ff926d86a024af6857988b10851a95f7},
isbn = {978-3-319-62127-2},
keywords = {conference myown publication},
pages = {265--276},
publisher = {Springer},
series = {Lecture Notes in Computer Science},
timestamp = {2017-09-13T10:18:24.000+0200},
title = {The Complexity of Drawing Graphs on Few Lines and Few Planes},
url = {https://doi.org/10.1007/978-3-319-62127-2_23},
year = 2017
}