Upper Bound Constructions for Untangling Planar Geometric Graphs

2014/01/01 by Javier Cano, Csaba D. Tóth, Jorge Urrutia · 8 citations
Computer Science · Engineering · Mathematics · #3D Modeling in Geospatial Applications #Combinatorics #Computational Geometry and Mesh Generation #Data Management and Algorithms #Discrete mathematics #Graph #Mathematical analysis #Mathematics #Planar #Planar graph #Upper and lower bounds #Vertex (graph theory)

paper · doi:10.1137/130924172

published in SIAM Journal on Discrete Mathematics 28(4), 1935-1943 (Society for Industrial and Applied Mathematics)

openalex publication_date 2014/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11

Abstract

For every n∈ ℕ, we construct an n-vertex planar graph G=(V,E) and n distinct points p(v), v∈ V, in the plane such that in any crossing-free straight-line drawing of G, at most O(n^.4948) vertices v∈ V are embedded at points p(v). This improves on an earlier bound of O(√(n)) by Goaoc et al. [Discrete Comput. Geom., 42 (2009), pp. 542--569].

Citations

• On Hamiltonian Circuits
• Convex Representations of Graphs
• The smallest non-hamiltonian 3-connected cubic planar graphs have 38 vertices
• Untangling a Polygon
• Untangling a Planar Graph

Cited by

• Planarity [wikipedia]