The Complexity Of An Algotithm For Plane Dual Of A Plane Graph

Dumitru Dan Burdescu

Abstract


The paper presents an algorithm for construction of a plane dual of a plane graph and its complexity. The dual graph is used in planar graph theory and planar separator. Many other algorithms of planar graphs may be based on this proposed algorithm. The treatment has a more combinatorial aspect than the classical treatment.