Progress on partial edge drawings


Dateien zu dieser Ressource

Dateien Größe Format Anzeige

Zu diesem Dokument gibt es keine Dateien.

BRUCKDORFER, Till, Sabine CORNELSEN, Carsten GUTWENGER, Michael KAUFMANN, Fabrizio MONTECCHIANI, Nöllenburg MARTIN, Alexander WOLFF, 2013. Progress on partial edge drawings. In: DIDIMO, Walter, ed., Maurizio PATRIGNANI, ed.. Graph Drawing. Berlin, Heidelberg:Springer Berlin Heidelberg, pp. 67-78. ISBN 978-3-642-36762-5

@inproceedings{Bruckdorfer2013Progr-26479, title={Progress on partial edge drawings}, year={2013}, doi={10.1007/978-3-642-36763-2_7}, number={7704}, isbn={978-3-642-36762-5}, address={Berlin, Heidelberg}, publisher={Springer Berlin Heidelberg}, series={Lecture Notes in Computer Science}, booktitle={Graph Drawing}, pages={67--78}, editor={Didimo, Walter and Patrignani, Maurizio}, author={Bruckdorfer, Till and Cornelsen, Sabine and Gutwenger, Carsten and Kaufmann, Michael and Montecchiani, Fabrizio and Martin, Nöllenburg, and Wolff, Alexander} }

Montecchiani, Fabrizio Graph Drawing : 20th International Symposium, GD 2012, Redmond, WA, USA, September 19-21, 2012 ; Revised Selected Papers / Walter Didimo and Maurizio Patrignani (eds.). - Berlin [u.a.] : Springer, 2013. - S. 67-78. - (Lecture notes in computer science ; 7704). - ISBN 978-3-642-36762-5 2014-02-26T09:26:18Z Bruckdorfer, Till Martin, Nöllenburg, Progress on partial edge drawings 2013 Wolff, Alexander Cornelsen, Sabine Wolff, Alexander eng Montecchiani, Fabrizio Kaufmann, Michael Gutwenger, Carsten Recently, a new way of avoiding crossings in straight-line drawings of non-planar graphs has been investigated. 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 a symmetric model (SPED) that requires 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 δ of the edge lengths (δ-SHPED). Given length and direction of a stub, this model helps to infer the position of the opposite stub.<br /><br /><br />We show that, for a fixed stub–edge length ratio δ, not all graphs have a δ-SHPED. Specifically, we show that K <sub>241</sub> does not have a 1/4-SHPED, while bandwidth-k graphs always have a Θ(1/k√) -SHPED. We also give bounds for complete bipartite graphs. Further, we consider the problem MaxSPED 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. Martin, Nöllenburg, Gutwenger, Carsten 2014-02-26T09:26:18Z Kaufmann, Michael Cornelsen, Sabine deposit-license Bruckdorfer, Till

Das Dokument erscheint in:

KOPS Suche


Mein Benutzerkonto