Geodesic
Progress on Partial Edge Drawings
Journal of Graph Algorithms and Applications, Tome 21 (2017) no. 4, pp. 757-786.

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

Recently, a new way of avoiding crossings in straight-line drawings of non-planar graphs has been introduced. The idea of partial edge drawings (PED) is to drop the middle part of edges and rely on the remaining edge parts called stubs. We focus on symmetric partial edge drawings (SPEDs) that require the two stubs of an edge to be of equal length. In this way, the stub at the other endpoint of an edge assures the viewer of the edge's existence. We also consider an additional homogeneity constraint that forces the stub lengths to be a given fraction $\delta$ of the edge lengths ($\delta$-SHPED). Given length and direction of a stub, this model helps to infer the position of the opposite stub. We show that, for a fixed stub–edge length ratio $\delta$, not all graphs have a $\delta$-SHPED. Specifically, we show that $K_{165}$ does not have a $1/4$-SHPED, while bandwidth-$k$ graphs always have a $\Theta(1/\sqrt{k})$-SHPED. We also give bounds for complete bipartite graphs. Further, we consider the problem ${\rm M{\small AX} SPED}$ where the task is to compute the SPED of maximum total stub length that a given straight-line drawing contains. We present an efficient solution for 2-planar drawings and a 2-approximation algorithm for the dual problem of minimizing the total amount of erased ink.
DOI : 10.7155/jgaa.00438
Keywords: Partial Edge Drawing, Graph Drawing, Network Visualization 
@article{JGAA_2017_21_4_a16,
     author = {Till Bruckdorfer and Sabine Cornelsen and Carsten Gutwenger and Michael Kaufmann and Fabrizio Montecchiani and Martin N\"ollenburg and Alexander Wolff},
     title = {Progress on {Partial} {Edge} {Drawings}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {757--786},
     publisher = {mathdoc},
     volume = {21},
     number = {4},
     year = {2017},
     doi = {10.7155/jgaa.00438},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00438/}
}
TY  - JOUR
AU  - Till Bruckdorfer
AU  - Sabine Cornelsen
AU  - Carsten Gutwenger
AU  - Michael Kaufmann
AU  - Fabrizio Montecchiani
AU  - Martin Nöllenburg
AU  - Alexander Wolff
TI  - Progress on Partial Edge Drawings
JO  - Journal of Graph Algorithms and Applications
PY  - 2017
SP  - 757
EP  - 786
VL  - 21
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00438/
DO  - 10.7155/jgaa.00438
LA  - en
ID  - JGAA_2017_21_4_a16
ER  - 
%0 Journal Article
%A Till Bruckdorfer
%A Sabine Cornelsen
%A Carsten Gutwenger
%A Michael Kaufmann
%A Fabrizio Montecchiani
%A Martin Nöllenburg
%A Alexander Wolff
%T Progress on Partial Edge Drawings
%J Journal of Graph Algorithms and Applications
%D 2017
%P 757-786
%V 21
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00438/
%R 10.7155/jgaa.00438
%G en
%F JGAA_2017_21_4_a16
Till Bruckdorfer; Sabine Cornelsen; Carsten Gutwenger; Michael Kaufmann; Fabrizio Montecchiani; Martin Nöllenburg; Alexander Wolff. Progress on Partial Edge Drawings. Journal of Graph Algorithms and Applications, Tome 21 (2017) no. 4, pp. 757-786. doi : 10.7155/jgaa.00438. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00438/

Cité par Sources :