2026-08-21T18:34:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27404 2026-08-21T14:42:38Z ddc:004 open_access

Connectivity Augmentation of Plane Graphs Dehaleesan, Krishnan Khan, Asif Misra, Pranabendu Connectivity augmentation Plane graphs Bridgetree BC-tree Balanced graph We study the problem of connectivity augmentation of a planar graph, while preserving planarity. This problem is motivated by many real-world settings such as road-networks, power-networks etc. In these settings, it is crucial to preserve the original planar embedding after augmentation. In 2009, Gutwenger and Mutzel gave a constructive algorithm showing that a connected planar graph with a fixed embedding (a plane graph) can be optimally augmented to a biconnected graph without crossings while preserving the embedding. We further this line of research, by giving an algorithm that computes a minimum set of edges that makes a connected plane graph 2-edge-connected in O(|V|(1+α(|V|))) time and linear space, where α is the inverse Ackermann function. We also study the 3-vertex-connectivity augmentation of biconnected outerplanar plane graphs. We present the first polynomial-time algorithm that augments such graphs to 3-connectivity with the minimum number of edges in O(|V|(1+α(|V|))) time and linear space while preserving the embedding, i.e. the augmented graph has a planar embedding that extends the given embedding. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Krishnan Dehaleesan and Asif Khan and Pranabendu Misra 2026 Is Part Of LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2026.23 urn:nbn:de:0030-drops-274044 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.23 eng https://creativecommons.org/licenses/by/4.0/legalcode