[Back]

M. Höller, F. Klute, S. Nickel, M. Nöllenburg, B. Schreiber:
"Maximizing Ink in Symmetric Partial Edge Drawings of k-plane Graphs";
Talk: European Workshop on Computational Geometry (EuroCG'18), Berlin; 2018-03-21 - 2018-03-23.

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. We study symmetric partial edge drawings (SPEDs), in which 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 drawing with crossings into a SPED is tractable for 2-plane input drawings, but generally NP-hard. We show that the problem remains NP-hard even for 3-plane input drawings. Yet, for k-plane input drawings whose edge intersection graph forms a collection of trees or cacti we present efficient algorithms for ink maximization.

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. We study symmetric partial edge drawings (SPEDs), in which 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 drawing with crossings into a SPED is tractable for 2-plane input drawings, but generally NP-hard. We show that the problem remains NP-hard even for 3-plane input drawings. Yet, for k-plane input drawings whose edge intersection graph forms a collection of trees or cacti we present efficient algorithms for ink maximization.