Publication:2333805

DOI10.1007/978-3-319-18173-8_11zbMath1436.68231DBLPconf/ciac/LozzoR15arXiv1501.07106OpenAlexW4206638026WikidataQ62046553 ScholiaQ62046553MaRDI QIDQ2333805

Ignaz Rutter, Giordano Da Lozzo

Publication date: 13 November 2019

Published in: Theoretical Computer Science, Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: In this paper we introduce a notion of planarity for graphs that are presented in a streaming fashion. A $ extit{streamed graph}$ is a stream of edges $e_1,e_2,...,e_m$ on a vertex set $V$. A streamed graph is $omega$-$ extit{stream planar}$ with respect to a positive integer window size $omega$ if there exists a sequence of planar topological drawings $Gamma_i$ of the graphs $G_i=(V,{e_j mid ileq j < i+omega})$ such that the common graph $G^{i}_cap=G_icap G_{i+1}$ is drawn the same in $Gamma_i$ and in $Gamma_{i+1}$, for $1leq i < m-omega$. The $ extit{Stream Planarity}$ Problem with window size $omega$ asks whether a given streamed graph is $omega$-stream planar. We also consider a generalization, where there is an additional $ extit{backbone graph}$ whose edges have to be present during each time step. These problems are related to several well-studied planarity problems. We show that the $ extit{Stream Planarity}$ 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 $omega ge 2$. On the positive side, we provide $O(n+omega{}m)$-time algorithms for (i) the case $omega = 1$ and (ii) all values of $omega$ 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((nm)^3)$-time algorithm proposed by Schaefer [GD'14] for $omega=1$.

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

zbMATH Keywords

planaritygraph drawingsimultaneous embeddingsstreamed graphs

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Online algorithms; streaming algorithms (68W27)

Cites Work

• Unnamed Item
• Drawing trees in a streaming model
• Testing the simultaneous embeddability of two graphs whose intersection is a biconnected or a connected graph
• Algorithms and bounds for drawing non-planar graphs with crossing-free subgraphs
• A linear-time algorithm for a special case of disjoint set union
• String graphs. II: Recognizing string graphs is NP-hard
• Simultaneous embedding: edge orderings, relative positions, cutvertices
• Planarity of streamed graphs
• Advancements on SEFE and partitioned book embedding problems
• Drawing Non-Planar Graphs with Crossing-Free Subgraphs
• Picking Planar Edges; or, Drawing a Graph with a Planar Subgraph
• Fast Algorithms for Finding Nearest Common Ancestors
• Simultaneous Graph Embeddings with Fixed Edges
• On-Line Planarity Testing
• Recognizing string graphs in NP

Related Items (11)

Hanani--Tutte and Hierarchical Partial Planarity ⋮ On the complexity of the storyplan problem ⋮ On the complexity of the storyplan problem ⋮ Small Point-Sets Supporting Graph Stories ⋮ Small point-sets supporting graph stories ⋮ Algorithms and bounds for drawing non-planar graphs with crossing-free subgraphs ⋮ Graph Stories in Small Area ⋮ Graph stories in small area ⋮ Hierarchical partial planarity ⋮ Approximation Algorithms for Facial Cycles in Planar Embeddings ⋮ Planarity of streamed graphs

Uses Software

• Algorithm 447

This page was built for publication: Planarity of streamed graphs