Level-Planar Drawings with Few Slopes

2019/07/31 by Brückner, Guido, Krisam, Nadine Davina, Mchedlidze, Tamara · 1 citation
#Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1907.13558

Abstract

We introduce and study level-planar straight-line drawings with a fixed number λ of slopes. For proper level graphs, we give an O(n log² n / log log n)-time algorithm that either finds such a drawing or determines that no such drawing exists. Moreover, we consider the partial drawing extension problem, where we seek to extend an immutable drawing of a subgraph to a drawing of the whole graph, and the simultaneous drawing problem, which asks about the existence of drawings of two graphs whose restrictions to their shared subgraph coincide. We present O(n^4/3 log n)-time and O(λ n^10/3 log n)-time algorithms for these respective problems on proper level-planar graphs. We complement these positive results by showing that testing whether non-proper level graphs admit level-planar drawings with λ slopes is \textsfNP-hard even in restricted cases.

Cited by

• On the 2-Bend Slope Number of 1-Planar Graphs

Related

• Drawing planar graphs of bounded degree with few slopes
• Upward Planar Drawings with Three and More Slopes
• Weakly Leveled Planarity with Bounded Span
• Graph drawings with one bend and few slopes
• Constrained Level Planarity is FPT with Respect to the Vertex Cover Number