TESTING MUTUAL DUALITY OF PLANAR GRAPHS

DOI10.1142/S0218195914600103zbMATH Open1332.05135arXiv1303.1640MaRDI QIDQ5261018FDOQ5261018

Thomas Bläsius, Ignaz Rutter, Patrizio Angelini

Publication date: 1 July 2015

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

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$.

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

zbMATH Keywords

dualitylinear-time algorithmplanar embedding

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (6)

• Maintaining triconnected components under node expansion
• Maintaining triconnected components under node expansion
• Decremental SPQR-trees for Planar Graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Testing Planarity of Partially Embedded Graphs

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)