2018/07/31 by Radermacher, Marcel, Rutter, Ignaz
#Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1807.11711
The algorithm of Gutwenger et al. to insert an edge e in linear time into a planar graph G with a minimal number of crossings on e, is a helpful tool for designing heuristics that minimize edge crossings in drawings of general graphs. Unfortunately, some graphs do not have a geometric embedding Γ such that Γ+e has the same number of crossings as the embedding G+e. This motivates the study of the computational complexity of the following problem: Given a combinatorially embedded graph G, compute a geometric embedding Γ that has the same combinatorial embedding as G and that minimizes the crossings of Γ+e. We give polynomial-time algorithms for special cases and prove that the general problem is fixed-parameter tractable in the number of crossings. Moreover, we show how to approximate the number of crossings by a factor (Δ-2), where Δ is the maximum vertex degree of G.