Home  Issues  Aims and Scope  Instructions for Authors 
DOI: 10.7155/jgaa.00438
Progress on Partial Edge Drawings
Till Bruckdorfer,
Sabine Cornelsen,
Carsten Gutwenger,
Michael Kaufmann,
Fabrizio Montecchiani,
Martin Nöllenburg, and
Alexander Wolff
Vol. 21, no. 4, pp. 757786, 2017. Regular paper.
Abstract Recently, a new way of avoiding crossings in straightline drawings
of nonplanar 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 straightline drawing contains. We present an efficient solution for 2planar drawings and a 2approximation algorithm for the dual problem of minimizing the total amount of erased ink. 
Submitted: October 2016.
Reviewed: April 2017.
Revised: June 2017.
Reviewed: August 2017.
Revised: August 2017.
Accepted: August 2017.
Final: August 2017.
Published: September 2017.
Communicated by
Csaba D. Tóth
