[Back]

M. Hummel, F. Klute, S. Nickel, M. Nöllenburg:
"Maximizing Ink in Partial Edge Drawings of k-plane Graphs";
Talk: International Symposium on Graph Drawing and Network Visualization (GD), Prag; 2019-09-17 - 2019-09-20; in: "GD 2019: Graph Drawing and Network Visualization", LNCS, 11904 (2019), ISBN: 978-3-030-35801-3; 323 - 336.

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.

http://dx.doi.org/10.1007/978-3-030-35802-0_25

https://publik.tuwien.ac.at/files/publik_284617.pdf