DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2026.23

Connectivity Augmentation of Plane Graphs

Authors: Krishnan Dehaleesan, Asif Khan, and Pranabendu Misra

Published in: LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)

Abstract

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.

Cite as

Krishnan Dehaleesan, Asif Khan, and Pranabendu Misra. Connectivity Augmentation of Plane Graphs. In 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 386, pp. 23:1-23:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{dehaleesan_et_al:LIPIcs.MFCS.2026.23,
  author =	{Dehaleesan, Krishnan and Khan, Asif and Misra, Pranabendu},
  title =	{{Connectivity Augmentation of Plane Graphs}},
  booktitle =	{51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)},
  pages =	{23:1--23:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-442-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{386},
  editor =	{Kouck\'{y}, Michal and Petrișan, Daniela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.23},
  URN =		{urn:nbn:de:0030-drops-274044},
  doi =		{10.4230/LIPIcs.MFCS.2026.23},
  annote =	{Keywords: Connectivity augmentation, Plane graphs, Bridgetree, BC-tree, Balanced graph}
}

Search Results

Documents authored by Dehaleesan, Krishnan

Connectivity Augmentation of Plane Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message