Geodesic
Drawing Planar Graphs with Few Geometric Primitives
Journal of Graph Algorithms and Applications, Tome 22 (2018) no. 2, pp. 357-387.

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

We define the visual complexity of a plane graph drawing to be the number of basic geometric objects needed to represent all its edges. In particular, one object may represent multiple edges (e.g., one needs only one line segment to draw a path with an arbitrary number of edges). Let $n$ denote the number of vertices of a graph. We show that trees can be drawn with $3n/4$ straight-line segments on a polynomial grid, and with $n/2$ straight-line segments on a quasi-polynomial grid. Further, we present an algorithm for drawing planar 3-trees with $(8n-17)/3$ segments on an $O(n)\times O(n^2)$ grid. This algorithm can also be used with a small modification to draw maximal outerplanar graphs with $3n/2$ edges on an $O(n)\times O(n^2)$ grid. We also study the problem of drawing maximal planar graphs with circular arcs and provide an algorithm to draw such graphs using only $(5n - 11)/3$ arcs. This is significantly smaller than the lower bound of $2n$ for line segments for a nontrivial graph class. 
@article{JGAA_2018_22_2_a8,
     author = {Gregor H\"ultenschmidt and Philipp Kindermann and Wouter Meulemans and Andr\'e Schulz},
     title = {Drawing {Planar} {Graphs} with {Few} {Geometric} {Primitives}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {357--387},
     publisher = {mathdoc},
     volume = {22},
     number = {2},
     year = {2018},
     doi = {10.7155/jgaa.00473},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00473/}
}
TY  - JOUR
AU  - Gregor Hültenschmidt
AU  - Philipp Kindermann
AU  - Wouter Meulemans
AU  - André Schulz
TI  - Drawing Planar Graphs with Few Geometric Primitives
JO  - Journal of Graph Algorithms and Applications
PY  - 2018
SP  - 357
EP  - 387
VL  - 22
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00473/
DO  - 10.7155/jgaa.00473
LA  - en
ID  - JGAA_2018_22_2_a8
ER  - 
%0 Journal Article
%A Gregor Hültenschmidt
%A Philipp Kindermann
%A Wouter Meulemans
%A André Schulz
%T Drawing Planar Graphs with Few Geometric Primitives
%J Journal of Graph Algorithms and Applications
%D 2018
%P 357-387
%V 22
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00473/
%R 10.7155/jgaa.00473
%G en
%F JGAA_2018_22_2_a8
Gregor Hültenschmidt; Philipp Kindermann; Wouter Meulemans; André Schulz. Drawing Planar Graphs with Few Geometric Primitives. Journal of Graph Algorithms and Applications, Tome 22 (2018) no. 2, pp. 357-387. doi : 10.7155/jgaa.00473. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00473/

Cité par Sources :