Aug 2026· International Symposium on Mathematical Foundations of Computer Science· pp. 23:1-23:16· 0 citations· 23 references
Computer Science
TL;DR
An algorithm is given that computes a minimum set of edges that makes a connected plane graph 2-edge-connected in \(O(|V|(1+\alpha(|V|)))\) time and linear space, where \(\alpha\) is the inverse Ackermann function.
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+\alpha(|V|)))\) time and linear space, where \(\alpha\) is the inverse Ackermann function.
For a graph and a graph family , let denote the maximum number of copies of in an ‐free ‐vertex graph. Let . Bai, Tompkins, and Well conjectured that is attained if and each block of the graph is a . In this paper, we determine the exact value of and the extremal graphs for all . The novelty of our proof is to give a...
Xiaojun Zhao, Yuejian Peng· Journal of Graph Theory· 2 citations
A graph is 1-planar if it has a drawing in which every edge is crossed at most once. We show that the smallest cubic non-1-planar graphs have $30$ vertices. Two such graphs are the Tutte-Coxeter graph of girth eight and a graph of girth seven that we call the Byte graph. Every subcubic graph with fewer than $30$ vertic...
A graph is 2-planar if it can be drawn in the plane such that each edge is crossed by at most two other edges. It is known that for a 2-planar graph $G$, $|E(G)| \le 5|V(G)| - 10$. When the equality holds, we call $G$ an optimal 2-planar graph. This paper investigates the matching extendability of optimal 2-planar grap...
An edge card of a graph is obtained by deleting one edge, and a class edge-reconstruction number asks for the fewest carefully selected cards that identify the graph when its class is known. We determine the sharp universal bound for maximal planar graphs. Two selected cards always suffice, and the octahedral graph sho...
The study of graph connectedness is a central topic in graph theory, with CF-connectedness being a specialized property of interest. A simple graph is CF-connected if it is connected and, in each of its optimal drawings, any two of its distinct vertices can be connected by a path consisting of uncrossed edges. This pap...
M. Staš, M. Švecová, Jana Fortes· Mathematics· 0 citations
The restricted edge-connectivity of a graph is the minimum size of an edge-cut whose removal leaves every component with at least two vertices. In 2024, Zhang et al. showed that the restricted edge-connectivity of any optimal $1$-planar graph belongs to $\{8,10,12\}$. In this paper, we exclude $8$ as a possible value,...
Licheng Zhang, Z. Ouyang, Yuan-Qiu Huang et al.· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
