Disconnectivity and relative positions in simultaneous embeddings

DOI10.1016/j.comgeo.2015.02.002zbMath1370.05047arXiv1204.2903OpenAlexW2069330400MaRDI QIDQ2349740

Ignaz Rutter, Thomas Bläsius

Publication date: 17 June 2015

Published in: Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

algorithmplanaritysimultaneous embeddingembedding representation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

Synchronized Planarity with Applications to Constrained Planarity Problems, Simultaneous Orthogonal Planarity, Simultaneous embedding: edge orderings, relative positions, cutvertices, Simultaneous Embeddings with Few Bends and Crossings, Hierarchical partial planarity, NodeTrix planarity testing with small clusters, Simultaneous Embedding

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Testing the simultaneous embeddability of two graphs whose intersection is a biconnected or a connected graph
• Characterizations of restricted pairs of planar graphs allowing simultaneous embedding with fixed edges
• A linear-time algorithm for a special case of disjoint set union
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• On-line maintenance of triconnected components with SPQR-trees
• Testing Simultaneous Planarity When the Common Graph Is 2-Connected
• Intersection Graphs in Simultaneous Embedding with Fixed Edges
• Fast Algorithms for Finding Nearest Common Ancestors
• Simultaneous Graph Embeddings with Fixed Edges
• An SPQR-Tree Approach to Decide Special Cases of Simultaneous Embedding with Fixed Edges
• On the Complexity of Timetable and Multicommodity Flow Problems
• On-Line Planarity Testing
• Toward a Theory of Planarity: Hanani-Tutte and Planarity Variants
• Simultaneous PQ-Ordering with Applications to Constrained Embedding Problems