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

DOI10.1016/J.JDA.2011.12.015MaRDI QIDQ450560zbMATH OpenOpenAlexWikidataFDO

Authors Patrizio Angelini, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani, 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)

Recommendations

• Testing the simultaneous embeddability of two graphs whose intersection is a biconnected graph or a tree
• Intersection Graphs in Simultaneous Embedding with Fixed Edges
• Disconnectivity and relative positions in simultaneous embeddings
• Simultaneous embedding of embedded planar graphs
• Characterizations of Restricted Pairs of Planar Graphs Allowing Simultaneous Embedding with Fixed Edges

Cites work

• scientific article; zbMATH DE number 2080088 (Why is no real title available?)
• 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
• An SPQR-Tree Approach to Decide Special Cases of Simultaneous Embedding with Fixed Edges
• Characterizations of Restricted Pairs of Planar Graphs Allowing Simultaneous Embedding with Fixed Edges
• Embedding Graphs Simultaneously with Fixed Edges
• Fast Algorithms for Finding Nearest Common Ancestors
• Intersection Graphs in Simultaneous Embedding with Fixed Edges
• On a tree and a path with no geometric simultaneous embedding
• On simultaneous planar graph embeddings
• On-Line Planarity Testing
• On-line maintenance of triconnected components with SPQR-trees
• SIMULTANEOUS EMBEDDING OF OUTERPLANAR GRAPHS, PATHS, AND CYCLES
• Simultaneous Embedding of Planar Graphs with Few Bends
• Simultaneous Geometric Graph Embeddings
• Simultaneous Graph Embeddings with Fixed Edges
• Testing planarity of partially embedded graphs
• Testing simultaneous planarity when the common graph is 2-connected
• Two trees which are self-intersecting when drawn simultaneously

Cited in

(28)

• Clustered planarity = flat clustered planarity
• On 3-coloring circle graphs
• An SPQR-Tree Approach to Decide Special Cases of Simultaneous Embedding with Fixed Edges
• Relaxing the constraints of clustered planarity
• Disconnectivity and relative positions in simultaneous embeddings
• An annotated review on graph drawing and its applications
• Simultaneous orthogonal planarity
• Simpler algorithms for testing two-page book embedding of partitioned graphs
• Simultaneous embedding of embedded planar graphs
• Disconnectivity and relative positions in simultaneous embeddings
• Testing the simultaneous embeddability of two graphs whose intersection is a biconnected graph or a tree
• Upward book embeddings of st-graphs
• Upward book embeddability of \(st\)-graphs: complexity and algorithms
• Stack-number is not bounded by queue-number
• scientific article; zbMATH DE number 7765366 (Why is no real title available?)
• Atomic Embeddability, Clustered Planarity, and Thickenability
• On 3-coloring circle graphs
• Testing simultaneous planarity when the common graph is 2-connected
• An annotated bibliography on 1-planarity
• Testing bipartiteness of geometric intersection graphs
• The importance of being proper
• Simultaneous embeddings with few bends and crossings
• Algorithms and bounds for drawing non-planar graphs with crossing-free subgraphs
• Testing simultaneous planarity when the common graph is 2-connected
• Simultaneous Embedding
• Topological morphing of planar graphs
• Drawing Simultaneously Embedded Graphs with Few Bends
• Advancements on SEFE and partitioned book embedding problems

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

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