Testing mutual duality of planar graphs

DOI10.1142/S0218195914600103MaRDI QIDQ5261018zbMATH OpenFDO

Authors Patrizio Angelini, Thomas Bläsius, Ignaz Rutter

Publication date 1 July 2015

Published in International Journal of Computational Geometry & Applications (Search for Journal in Brave)

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

zbMATH Keywords

dualitylinear-time algorithmplanar embedding

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: We introduce and study the problem mpd, which asks for two planar graphs $G_1$ and $G_2$ whether $G_1$ can be embedded such that its dual is isomorphic to $G_2$. Our algorithmic main result is an NP-completeness proof for the general case and a linear-time algorithm for biconnected graphs. To shed light onto the combinatorial structure of the duals of a planar graph, we consider the emph{common dual relation} $sim$, where $G_{1}sim{G}_2$ if and only if they have a common dual. While $sim$ is generally not transitive, we show that the restriction to biconnected graphs is an equivalence relation. In this case, being dual to each other carries over to the equivalence classes, i.e., two graphs are dual to each other if and only if any two elements of their respective equivalence classes are dual to each other. To achieve the efficient testing algorithm for mpd on biconnected graphs, we devise a succinct representation of the equivalence class of a biconnected planar graph. It is similar to SPQR-trees and represents exactly the graphs that are contained in the equivalence class. The testing algorithm then works by testing in linear time whether two such representations are isomorphic. We note that a special case of mpd is testing whether a graph $G$ is self-dual. Our algorithm handles the case where $G$ is biconnected and our NP-hardness proof extends to testing self-duality of general planar graphs and also to testing map self-duality, where a graph $G$ is map self-dual if it admits a planar embedding $mathcalG$ such that $G^{s}tar$ is isomorphic to $G$, and additionally the embedding induced by $mathcalG$ on $G^{s}tar$ is $mathcalG$.

Recommendations

• Testing Mutual Duality of Planar Graphs
• scientific article; zbMATH DE number 496022
• scientific article; zbMATH DE number 861336
• scientific article; zbMATH DE number 975400
• Testing simultaneous planarity when the common graph is 2-connected

Cites work

• 2-Isomorphic Graphs
• Congruent Graphs and the Connectivity of Graphs
• Connectivity in Matroids
• Construction of Self-Dual Graphs
• Finding a minimum-depth embedding of a planar graph in \(O(n^{4})\) time
• On the complexity of embedding planar graphs to minimize certain distance measures
• On the complexity of matroid isomorphism problem
• On-Line Planarity Testing
• Self-dual graphs
• The construction and classification of self-dual spherical polyhedra

Cited in

(6)

• scientific article; zbMATH DE number 496022 (Why is no real title available?)
• Testing Planarity of Partially Embedded Graphs
• Decremental SPQR-trees for Planar Graphs
• Maintaining triconnected components under node expansion
• scientific article; zbMATH DE number 7765366 (Why is no real title available?)
• Maintaining triconnected components under node expansion

This page was built for publication: Testing mutual duality of planar graphs

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