Planarity of streamed graphs

Abstract: In this paper we introduce a notion of planarity for graphs that are presented in a streaming fashion. A

e x t i t s t r e a m e d g r a p h

is a stream of edges

e_{1}, e_{2}, ..., e_{m}

on a vertex set

V

. A streamed graph is

o m e g a

-

e x t i t s t r e a m p l a n a r

with respect to a positive integer window size

o m e g a

if there exists a sequence of planar topological drawings

G a m m a_{i}

of the graphs

G_{i} = (V, e_{j} m i d i l e q j < i + o m e g a)

such that the common graph

G_{c}^{i} a p = G_{i} c a p G_{i + 1}

is drawn the same in

G a m m a_{i}

and in

G a m m a_{i + 1}

, for

1 l e q i < m - o m e g a

. The

e x t i t S t r e a m P l a n a r i t y

Problem with window size

o m e g a

asks whether a given streamed graph is

o m e g a

-stream planar. We also consider a generalization, where there is an additional

e x t i t b a c k b o n e g r a p h

whose edges have to be present during each time step. These problems are related to several well-studied planarity problems. We show that the

e x t i t S t r e a m P l a n a r i t y

Problem is NP-complete even when the window size is a constant and that the variant with a backbone graph is NP-complete for all

o m e g a g e 2

. On the positive side, we provide

O (n + o m e g a m)

-time algorithms for (i) the case

o m e g a = 1

and (ii) all values of

o m e g a

provided the backbone graph consists of one

2

-connected component plus isolated vertices and no stream edge connects two isolated vertices. Our results improve on the Hanani-Tutte-style

O ((n m)^{3})

-time algorithm proposed by Schaefer [GD'14] for

o m e g a = 1

.

Recommendations

Cites Work

Cited In (12)

Uses Software

This page was built for publication: Planarity of streamed graphs