Geodesic
Edge-weighted contact representations of planar graphs
Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the Twentieth International Symposium on Graph Drawing, GD 2012 , Tome 17 (2013) no. 4, pp. 441-473.

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

We study contact representations of edge-weighted planar graphs, where vertices are represented as interior-disjoint rectangles or rectilinear polygons and edges are represented as contacts of vertex boundaries whose contact lengths represent the edge weights. For the case of rectangles, we show that, for any given edge-weighted planar graph whose outer face is a quadrangle, that is internally triangulated and that has no separating triangles, we can construct in linear time an edge-proportional rectangular dual (contact lengths are equal to the given edge weights and the union of all rectangles is again a rectangle) or report failure if none exists. In the case of arbitrarily many outer vertices, we show that deciding whether a square layout exists is NP-complete. If the orientation of each contact is specified by a so-called regular edge labeling and edge weights are lower bounds on the contact lengths, a corresponding rectangular dual that minimizes the area and perimeter of the enclosing rectangle can be found in linear time. On the other hand, without a given regular edge labeling, the same problem is NP-complete, as is the question whether a rectangular dual exists given lower and upper bounds on the contact lengths. For the case of rectilinear polygons, we give a complete characterization of the polygon complexity required for representing connected internally triangulated graphs: For outerplanar graphs and graphs with a single inner vertex polygon, complexity 8 is sufficient and necessary, and for graphs with two adjacent or multiple non-adjacent internal vertices the required polygon complexity is unbounded.
DOI : 10.7155/jgaa.00299
Keywords: graph drawing, contact representations, edge-weighted graphs, cartograms 
@article{JGAA_2013_17_4_a2,
     author = {Martin N\"ollenburg and Prutkin Roman and Ignaz Rutter},
     title = {Edge-weighted contact representations of planar graphs},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {441--473},
     publisher = {mathdoc},
     volume = {17},
     number = {4},
     year = {2013},
     doi = {10.7155/jgaa.00299},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00299/}
}
TY  - JOUR
AU  - Martin Nöllenburg
AU  - Prutkin Roman
AU  - Ignaz Rutter
TI  - Edge-weighted contact representations of planar graphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2013
SP  - 441
EP  - 473
VL  - 17
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00299/
DO  - 10.7155/jgaa.00299
LA  - en
ID  - JGAA_2013_17_4_a2
ER  - 
%0 Journal Article
%A Martin Nöllenburg
%A Prutkin Roman
%A Ignaz Rutter
%T Edge-weighted contact representations of planar graphs
%J Journal of Graph Algorithms and Applications
%D 2013
%P 441-473
%V 17
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00299/
%R 10.7155/jgaa.00299
%G en
%F JGAA_2013_17_4_a2
Martin Nöllenburg; Prutkin Roman; Ignaz Rutter. Edge-weighted contact representations of planar graphs. Journal of Graph Algorithms and Applications, 
							Special Issue on Selected Papers from the Twentieth International Symposium on Graph Drawing, GD 2012
					, Tome 17 (2013) no. 4, pp. 441-473. doi : 10.7155/jgaa.00299. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00299/

Cité par Sources :