Geodesic
Inapproximability of Orthogonal Compaction
Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the Nineteenth International Symposium on Graph Drawing, GD 2011 , Tome 16 (2012) no. 3, pp. 651-673.

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

We show that several problems of compacting orthogonal graph drawings to use the minimum number of rows, area, length of longest edge or total edge length cannot be approximated better than within a polynomial factor of optimal in polynomial time unless P=NP. We also provide a fixed-parameter-tractable algorithm for testing whether a drawing can be compacted to a small number of rows. 
@article{JGAA_2012_16_3_a2,
     author = {Michael Bannister and David Eppstein and Joseph Simons},
     title = {Inapproximability of {Orthogonal} {Compaction}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {651--673},
     publisher = {mathdoc},
     volume = {16},
     number = {3},
     year = {2012},
     doi = {10.7155/jgaa.00263},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00263/}
}
TY  - JOUR
AU  - Michael Bannister
AU  - David Eppstein
AU  - Joseph Simons
TI  - Inapproximability of Orthogonal Compaction
JO  - Journal of Graph Algorithms and Applications
PY  - 2012
SP  - 651
EP  - 673
VL  - 16
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00263/
DO  - 10.7155/jgaa.00263
LA  - en
ID  - JGAA_2012_16_3_a2
ER  - 
%0 Journal Article
%A Michael Bannister
%A David Eppstein
%A Joseph Simons
%T Inapproximability of Orthogonal Compaction
%J Journal of Graph Algorithms and Applications
%D 2012
%P 651-673
%V 16
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00263/
%R 10.7155/jgaa.00263
%G en
%F JGAA_2012_16_3_a2
Michael Bannister; David Eppstein; Joseph Simons. Inapproximability of Orthogonal Compaction. Journal of Graph Algorithms and Applications, 
							Special Issue on Selected Papers from the Nineteenth International Symposium on Graph Drawing, GD 2011
					, Tome 16 (2012) no. 3, pp. 651-673. doi : 10.7155/jgaa.00263. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00263/

Cité par Sources :