2007/06/07 by Xavier Goaoc, Goaoc, Xavier, Jan Kratochvı́l +8 · 1 citation
Computer Science · Engineering · #Algorithms and Data Compression #Computational Complexity (cs.CC) #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #VLSI and FPGA Design Techniques #cs.CC #cs.CG #cs.DM
paper · pdf · doi:10.48550/arxiv.0706.1002
This paper has been merged with http://arxiv.org/abs/0709.0170
openalex publication_date 2007/06/07 · arxiv created 2008/11/06 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A straight-line drawing δ of a planar graph G need not be plane, but can be made so by moving some of the vertices. Let shift(G,δ) denote the minimum number of vertices that need to be moved to turn δ into a plane drawing of G. We show that shift(G,δ) is NP-hard to compute and to approximate, and we give explicit bounds on shift(G,δ) when G is a tree or a general planar graph. Our hardness results extend to 1BendPointSetEmbeddability, a well-known graph-drawing problem.