Progress on partial edge drawings

DOI10.7155/JGAA.00438MaRDI QIDQ5367022zbMATH OpenOpenAlexFDO

Authors Till Bruckdorfer, Sabine Cornelsen, Carsten Gutwenger, Michael Kaufmann, Fabrizio Montecchiani, Martin Nöllenburg, Alexander Wolff

Publication date 12 October 2017

Published in Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1209.0830

zbMATH Keywords

2-approximation algorithm2-planar drawings\textsc{MaxSPED}SPED of maximum total stub length

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Abstract: Recently, a new way of avoiding crossings in straight-line drawings of non-planar graphs has been investigated. 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 a symmetric model (SPED) that requires 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_{241}$ does not have a 1/4-SHPED, while bandwidth-$k$ graphs always have a $Theta(1/sqrtk)$-SHPED. We also give bounds for complete bipartite graphs. Further, we consider the problem extsc{MaxSPED} where the task is to compute the SPED of maximum total stub length that a given straight-line drawing contains. We present an efficient solution for 2-planar drawings and a 2-approximation algorithm for the dual problem.

Recommendations

• Progress on partial edge drawings
• 1-bend orthogonal partial edge drawing
• Drawing partially embedded and simultaneously planar graphs
• The stub resolution of 1-planar graphs
• Drawing non-planar graphs with crossing-free subgraphs

Cited in

(10)

• Gap-planar graphs
• Efficient generation of different topological representations of graphs beyond-planarity
• Maximizing ink in partial edge drawings of \(k\)-plane graphs
• Exploring Complex Drawings via Edge Stratification
• Progress on partial edge drawings
• Crossing Layout in Non-planar Graph Drawings
• The stub resolution of 1-planar graphs
• Efficient generation of different topological representations of graphs beyond-planarity
• 1-bend orthogonal partial edge drawing
• Evaluating animation parameters for morphing edge drawings

This page was built for publication: Progress on partial edge drawings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5367022)