Compatible connectivity augmentation of planar disconnected graphs

DOI10.1007/S00454-015-9716-8MaRDI QIDQ894688zbMATHOpenAlexFDO

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

Publication date 2 December 2015

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

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

planar graphs graph drawing Euclidean minimum spanning trees

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

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,

m a t h c a l G

, that has

r g e 2

connected components, and

k g e 2

isomorphic planar straight-line drawings,

G_{1}, l d o t s, G_{k}

, of

m a t h c a l G

. We wish to augment

m a t h c a l G

by adding vertices and edges to make it connected in such a way that these vertices and edges can be added to

G_{1}, l d o t s, G_{k}

as points and straight-line segments, respectively, to obtain

k

planar straight-line drawings isomorphic to the augmentation of

m a t h c a l G

. We show that adding

T h e t a (n r^{1 - 1 / k})

edges and vertices to

m a t h c a l G

is always sufficient and sometimes necessary to achieve this goal. The upper bound holds for all

r i n 2, l d o t s, n

and

k g e 2

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

r i n 2, l d o t s, n / 4

and

k g e 2

.

Recommendations

Cites work

Cited in

(6)

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)