Testing simultaneous planarity when the common graph is 2-connected

DOI10.1007/978-3-642-17514-5_35MaRDI QIDQ3060792zbMATH OpenOpenAlexFDO

Authors Bernhard Haeupler, K. R. Jampani, Anna Lubiw

Publication date 9 December 2010

Published in Algorithms and Computation (Search for Journal in Brave)

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

zbMATH Keywords

planar graphgraph drawingsimultaneous embeddingPQ tree

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10)

Abstract: Two planar graphs G1 and G2 sharing some vertices and edges are `simultaneously planar' if they have planar drawings such that a shared vertex [edge] is represented by the same point [curve] in both drawings. It is an open problem whether simultaneous planarity can be tested efficiently. We give a linear-time algorithm to test simultaneous planarity when the two graphs share a 2-connected subgraph. Our algorithm extends to the case of k planar graphs where each vertex [edge] is either common to all graphs or belongs to exactly one of them.

Recommendations

• Testing simultaneous planarity when the common graph is 2-connected
• Characterizations of Restricted Pairs of Planar Graphs Allowing Simultaneous Embedding with Fixed Edges
• Testing the simultaneous embeddability of two graphs whose intersection is a biconnected or a connected graph
• Testing the simultaneous embeddability of two graphs whose intersection is a biconnected graph or a tree
• Disconnectivity and relative positions in simultaneous embeddings

Cited in

(5)

• Recognizing some subclasses of vertex intersection graphs of 0-bend paths in a grid
• Disconnectivity and relative positions in simultaneous embeddings
• Testing simultaneous planarity when the common graph is 2-connected
• Testing the simultaneous embeddability of two graphs whose intersection is a biconnected or a connected graph
• Testing Mutual Duality of Planar Graphs

This page was built for publication: Testing simultaneous planarity when the common graph is 2-connected

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3060792)