Compatible connectivity augmentation of planar disconnected graphs

DOI10.1007/S00454-015-9716-8zbMATH Open1326.05073arXiv1408.2436OpenAlexW2571115282MaRDI QIDQ894688FDOQ894688

Luis Barba, Greg Aloupis, Vida Dujmović, Pat Morin, Fabrizio Frati, Paz Carmi

Publication date: 2 December 2015

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Abstract: Motivated by applications to graph morphing, we consider the following emph{compatible connectivity-augmentation problem}: We are given a labelled $n$-vertex planar graph, $mathcalG$, that has $rge2$ connected components, and $kge2$ isomorphic planar straight-line drawings, $G_1,ldots,G_k$, of $mathcalG$. We wish to augment $mathcalG$ by adding vertices and edges to make it connected in such a way that these vertices and edges can be added to $G_1,ldots,G_k$ as points and straight-line segments, respectively, to obtain $k$ planar straight-line drawings isomorphic to the augmentation of $mathcalG$. We show that adding $Theta(n{r}^{1-1/k})$ edges and vertices to $mathcalG$ is always sufficient and sometimes necessary to achieve this goal. The upper bound holds for all $rin2,ldots,n$ and $kge2$ and is achievable by an algorithm whose running time is $O(n{r}^{1-1/k})$ for $k=O(1)$ and whose running time is $O(k{n}^2)$ for general values of $k$. The lower bound holds for all $rin2,ldots,n/4$ and $kge2$.

Full work available at URL: https://arxiv.org/abs/1408.2436

zbMATH Keywords

planar graphsgraph drawingEuclidean minimum spanning trees

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Connectivity (05C40) Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• An Analysis of Several Heuristics for the Traveling Salesman Problem
• A Delaunay Refinement Algorithm for Quality 2-Dimensional Mesh Generation
• Morphing Planar Graph Drawings Optimally
• Morphing Planar Graph Drawings with a Polynomial Number of Steps
• Deformations of Plane Rectilinear Complexes
• Graph Drawing
• Deformations of plane graphs
• The shortest path and the shortest road through n points
• Augmenting the connectivity of geometric graphs
• Finding the medial axis of a simple polygon in linear time
• Connectivity augmentation in planar straight line graphs
• Augmenting the Connectivity of Planar and Geometric Graphs
• On the Shortest Path Through a Number of Points
• On the length of optimal TSP circuits in sets of bounded diameter
• INTRINSIC MORPHING OF COMPATIBLE TRIANGULATIONS
• On compatible triangulations of simple polygons
• Über einen geometrischen Satz
• Graph Drawing in Motion
• ISOMORPHIC TRIANGULATIONS WITH SMALL NUMBER OF STEINER POINTS

Cited In (3)

• Title not available (Why is that?)
• Augmenting the connectivity of outerplanar graphs
• Optimal morphs of planar orthogonal drawings. II

This page was built for publication: Compatible connectivity augmentation of planar disconnected graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q894688)