Geodesic
The Complexity of Bendless Three-Dimensional Orthogonal Graph Drawing
Journal of Graph Algorithms and Applications, Tome 17 (2013) no. 1, pp. 35-55.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

We consider embeddings of 3-regular graphs into 3-dimensional Cartesian coordinates, in such a way that two vertices are adjacent if and only if two of their three coordinates are equal (that is, if they lie on an axis-parallel line) and such that no three points lie on the same axis-parallel line; we call a graph with such an embedding an xyz graph. We show that planar xyz graphs can be recognized in linear time, but that it is NP-complete to determine whether an arbitrary graph is an xyz graph. We also describe an algorithm with running time O(n2n/2) for testing whether a given n-vertex graph is an xyz graph.
DOI : 10.7155/jgaa.00283
Keywords: graph drawing, topological graph theory, 3-coloring, NP-completeness, exponential-time exact algorithms 
@article{JGAA_2013_17_1_a2,
     author = {David Eppstein},
     title = {The {Complexity} of {Bendless} {Three-Dimensional} {Orthogonal} {Graph} {Drawing}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {35--55},
     publisher = {mathdoc},
     volume = {17},
     number = {1},
     year = {2013},
     doi = {10.7155/jgaa.00283},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00283/}
}
TY  - JOUR
AU  - David Eppstein
TI  - The Complexity of Bendless Three-Dimensional Orthogonal Graph Drawing
JO  - Journal of Graph Algorithms and Applications
PY  - 2013
SP  - 35
EP  - 55
VL  - 17
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00283/
DO  - 10.7155/jgaa.00283
LA  - en
ID  - JGAA_2013_17_1_a2
ER  - 
%0 Journal Article
%A David Eppstein
%T The Complexity of Bendless Three-Dimensional Orthogonal Graph Drawing
%J Journal of Graph Algorithms and Applications
%D 2013
%P 35-55
%V 17
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00283/
%R 10.7155/jgaa.00283
%G en
%F JGAA_2013_17_1_a2
David Eppstein. The Complexity of Bendless Three-Dimensional Orthogonal Graph Drawing. Journal of Graph Algorithms and Applications, Tome 17 (2013) no. 1, pp. 35-55. doi : 10.7155/jgaa.00283. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00283/

Cité par Sources :