Simultaneous embedding: edge orderings, relative positions, cutvertices

DOI10.1007/s00453-017-0301-9zbMath1394.68263arXiv1506.05715OpenAlexW2614097238MaRDI QIDQ1751092

Thomas Bläsius, Annette Karrer, Ignaz Rutter

Publication date: 23 May 2018

Published in: Algorithmica, Graph Drawing (Search for Journal in Brave)

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

zbMATH Keywords

planar graphgraph drawingefficient algorithmplanar embeddingsimultaneous embedding

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (9)

Atomic Embeddability, Clustered Planarity, and Thickenability ⋮ Synchronized Planarity with Applications to Constrained Planarity Problems ⋮ Simultaneous Orthogonal Planarity ⋮ An SPQR-tree-like embedding representation for upward planarity ⋮ Simultaneous embedding: edge orderings, relative positions, cutvertices ⋮ Drawing Simultaneously Embedded Graphs with Few Bends ⋮ Simultaneous Embedding ⋮ Planarity of streamed graphs ⋮ Advancements on SEFE and partitioned book embedding problems

Cites Work

• Unnamed Item
• Testing the simultaneous embeddability of two graphs whose intersection is a biconnected or a connected graph
• A new perspective on clustered planarity as a combinatorial embedding problem
• A linear-time algorithm for a special case of disjoint set union
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Simultaneous embedding: edge orderings, relative positions, cutvertices
• On-line maintenance of triconnected components with SPQR-trees
• Disconnectivity and relative positions in simultaneous embeddings
• Toward a Theory of Planarity: Hanani-Tutte and Planarity Variants
• Intersection Graphs in Simultaneous Embedding with Fixed Edges
• Fast Algorithms for Finding Nearest Common Ancestors
• Simultaneous Graph Embeddings with Fixed Edges
• Short path queries in planar graphs in constant time
• Testing Simultaneous Planarity when the Common Graph is 2-Connected
• Simultaneous PQ-Ordering with Applications to Constrained Embedding Problems

This page was built for publication: Simultaneous embedding: edge orderings, relative positions, cutvertices