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.
%0 Book Section
%1 cflrvw-cdgfl-WADS17
%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)
%D 2017
%E Ellen, Faith
%E Kolokolova, Antonina
%E Sack, Jörg-Rüdiger
%I Springer-Verlag
%K "affinity myown number"
%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 http://dx.doi.org/10.1007/978-3-319-62127-2_23
%V 10389
%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{cflrvw-cdgfl-WADS17,
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-07-04T14:19:32.000+0200},
author = {Chaplick, Steven and Fleszar, Krzysztof and Lipp, Fabian and Ravsky, Alexander and Verbitsky, Oleg and Wolff, Alexander},
biburl = {https://www.bibsonomy.org/bibtex/2011bfa4b178509449d90757a21ca7ea3/fabianlipp},
booktitle = {Proc. Algorithms Data Struct. Symp. (WADS'17)},
doi = {10.1007/978-3-319-62127-2_23},
editor = {Ellen, Faith and Kolokolova, Antonina and Sack, Jörg-Rüdiger},
interhash = {a60ddbaa74f4f93956bf779200355549},
intrahash = {011bfa4b178509449d90757a21ca7ea3},
isbn = {978-3-319-62127-2},
keywords = {"affinity myown number"},
pages = {265--276},
publisher = {Springer-Verlag},
series = {Lecture Notes in Computer Science},
timestamp = {2017-07-04T14:19:32.000+0200},
title = {The Complexity of Drawing Graphs on Few Lines and Few Planes},
url = {http://dx.doi.org/10.1007/978-3-319-62127-2_23},
volume = 10389,
year = 2017
}