TESTING MUTUAL DUALITY OF PLANAR GRAPHS

DOI10.1142/S0218195914600103zbMath1332.05135arXiv1303.1640MaRDI QIDQ5261018

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)

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

zbMATH Keywords

dualityplanar embeddinglinear-time algorithm

Mathematics Subject Classification ID

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

Related Items (3)

Maintaining triconnected components under node expansion ⋮ Unnamed Item ⋮ Decremental SPQR-trees for Planar Graphs

Cites Work

• 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
• The construction and classification of self-dual spherical polyhedra
• Self-dual graphs
• Construction of Self-Dual Graphs
• Congruent Graphs and the Connectivity of Graphs
• On-Line Planarity Testing
• 2-Isomorphic Graphs
• Connectivity in Matroids

This page was built for publication: TESTING MUTUAL DUALITY OF PLANAR GRAPHS