Testing the simultaneous embeddability of two graphs whose intersection is a biconnected or a connected graph

DOI10.1016/j.jda.2011.12.015zbMath1247.05156OpenAlexW1985459410WikidataQ56689204 ScholiaQ56689204MaRDI QIDQ450560

Maurizio Patrignani, Fabrizio Frati, Giuseppe Di Battista, Patrizio Angelini, Ignaz Rutter

Publication date: 13 September 2012

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2011.12.015

zbMATH Keywords

planaritylinear-time algorithmSPQR-treesimultaneous embedding with fixed edges

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (24)

SIMULTANEOUS EMBEDDING OF EMBEDDED PLANAR GRAPHS ⋮ Stack-number is not bounded by queue-number ⋮ Atomic Embeddability, Clustered Planarity, and Thickenability ⋮ An annotated bibliography on 1-planarity ⋮ Topological morphing of planar graphs ⋮ Upward book embeddability of \(st\)-graphs: complexity and algorithms ⋮ An annotated review on graph drawing and its applications ⋮ Simultaneous Orthogonal Planarity ⋮ Algorithms and bounds for drawing non-planar graphs with crossing-free subgraphs ⋮ Unnamed Item ⋮ Clustered planarity = flat clustered planarity ⋮ Testing the Simultaneous Embeddability of Two Graphs Whose Intersection Is a Biconnected Graph or a Tree ⋮ Simpler algorithms for testing two-page book embedding of partitioned graphs ⋮ Simultaneous embedding: edge orderings, relative positions, cutvertices ⋮ Simultaneous Embeddings with Few Bends and Crossings ⋮ Relaxing the constraints of clustered planarity ⋮ Hierarchical partial planarity ⋮ The importance of being proper ⋮ Drawing Simultaneously Embedded Graphs with Few Bends ⋮ Upward Book Embeddings of st-Graphs ⋮ Simultaneous Embedding ⋮ Planarity of streamed graphs ⋮ Advancements on SEFE and partitioned book embedding problems ⋮ Disconnectivity and relative positions in simultaneous embeddings

Cites Work

• Unnamed Item
• Unnamed Item
• On simultaneous planar graph embeddings
• Two trees which are self-intersecting when drawn simultaneously
• 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
• On a Tree and a Path with No Geometric Simultaneous Embedding
• Intersection Graphs in Simultaneous Embedding with Fixed Edges
• Fast Algorithms for Finding Nearest Common Ancestors
• SIMULTANEOUS EMBEDDING OF OUTERPLANAR GRAPHS, PATHS, AND CYCLES
• Simultaneous Graph Embeddings with Fixed Edges
• Embedding Graphs Simultaneously with Fixed Edges
• An SPQR-Tree Approach to Decide Special Cases of Simultaneous Embedding with Fixed Edges
• On-Line Planarity Testing
• Simultaneous Embedding of Planar Graphs with Few Bends
• Characterizations of Restricted Pairs of Planar Graphs Allowing Simultaneous Embedding with Fixed Edges
• Simultaneous Geometric Graph Embeddings

This page was built for publication: Testing the simultaneous embeddability of two graphs whose intersection is a biconnected or a connected graph