2026-07-21T23:34:32Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25009 2026-02-09T07:53:31Z ddc:004 open_access

The Price of Connectivity Augmentation on Planar Graphs A. Akitaya, Hugo Dallant, Justin Demaine, Erik D. Kaufmann, Michael Kleist, Linda Stock, Frederick Tóth, Csaba D. Ueckerdt, Torsten connectivity augmentation local crossing number flip distance Given two classes of graphs, 𝒢₁ ⊆ 𝒢₂, and a c-connected graph G ∈ 𝒢₁, we wish to augment G with a smallest cardinality set of new edges F to obtain a k-connected graph G' = (V,E∪ F) ∈ 𝒢₂. In general, this is the c → k connectivity augmentation problem. Previous research considered variants where 𝒢₁ = 𝒢₂ is the class of planar graphs, plane graphs, or planar straight-line graphs. In all three settings, we prove that the c → k augmentation problem is NP-complete when 2 ≤ c < k ≤ 5. However, the connectivity of the augmented graph G' is at most 5 if 𝒢₂ is limited to planar graphs. We initiate the study of the c → k connectivity augmentation problem for arbitrary k ∈ ℕ, where 𝒢₁ is the class of planar graphs, plane graphs, or planar straight-line graphs, and 𝒢₂ is a beyond-planar class of graphs: 𝓁-planar, 𝓁-plane topological, or 𝓁-plane geometric graphs. We obtain tight bounds on the tradeoffs between the desired connectivity k and the local crossing number 𝓁 of the augmented graph G'. We also show that our hardness results apply to this setting. The connectivity augmentation problem for triangulations is intimately related to edge flips; and the minimum augmentation problem to the flip distance between triangulations. We prove that it is NP-complete to find the minimum flip distance between a given triangulation and a 4-connected triangulation, settling an open problem posed in 2014, and present an EPTAS for this problem. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hugo A. Akitaya and Justin Dallant and Erik D. Demaine and Michael Kaufmann and Linda Kleist and Frederick Stock and Csaba D. Tóth and Torsten Ueckerdt 2025 Is Part Of LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.GD.2025.23 urn:nbn:de:0030-drops-250095 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.23 eng https://creativecommons.org/licenses/by/4.0/legalcode