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

Created from the Publication Database of the Vienna University of Technology.