  Partial edge drawing (PED) is a drawing style for non-planar graphs, in which
edges are drawn only partially as pairs of opposing stubs on the respective
end-vertices. In a PED, by erasing the central parts of edges, all edge
crossings and the resulting visual clutter are hidden in the undrawn parts of
the edges. In symmetric partial edge drawings (SPEDs), the two stubs of each
edge are required to have the same length. It is known that maximizing the ink
(or the total stub length) when transforming a straight-line graph drawing with
crossings into a SPED is tractable for 2-plane input drawings, but NP-hard for
unrestricted inputs. We show that the problem remains NP-hard even for 3-plane
input drawings and establish NP-hardness of ink maximization for PEDs of
4-plane graphs. Yet, for k-plane input drawings whose edge intersection graph
forms a collection of trees or, more generally, whose intersection graph has
bounded treewidth, we present efficient algorithms for computing maximum-ink
PEDs and SPEDs. We implemented the treewidth-based algorithms and show a brief
experimental evaluation.
