Progress on Partial Edge DrawingsBruckdorfer, Till and Cornelsen, Sabine and Gutwenger, Carsten and Kaufmann, Michael and Montecchiani, Fabrizio and Nöllenburg, Martin and Wolff, Alexander (2013) Progress on Partial Edge Drawings. In: 20th International Symposium, GD 2012, September 1921, 2012 , pp. 6778(Official URL: http://link.springer.com/chapter/10.1007/9783642...). Full text not available from this repository.
Official URL: http://link.springer.com/chapter/10.1007/9783642...
AbstractRecently, a new way of avoiding crossings in straightline drawings of nonplanar 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. We show that, for a fixed stubedge length ratio δ, not all graphs have a δSHPED. Specifically, we show that $K_241$ does not have a 1/4SHPED, while bandwidthk graphs always have a $\Theta(1/\sqrt{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 straightline drawing contains. We present an efficient solution for 2planar drawings and a 2approximation algorithm for the dual problem.
Actions (login required)
