Planarity of streamed graphs

DOI10.1016/j.tcs.2019.09.029zbMath1436.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)

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)

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

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

This page was built for publication: Planarity of streamed graphs