Algorithms to Obtain a Maximal Planar Hamilton Subgraph

Noriya KOBAYASHI, Sumio MASUDA, Toshinobu KASHIWABARA

Summary :

In this paper we present polynomial time algorithms for the following three problems on a Hamilton graph with a prescribed Hamilton circuit: (1) Given a Hamilton graph G with a prescribed Hamilton circuit, find a maximal planar Hamilton subgraph of G, (2) Given a Hamilton graph G and a planar Hamilton subgraph H of G, find a maximal planar Hamilton subgraph of G that contains H, and (3) Given an edge-weighted Hamilton graph G=(V, E), find a planar Hamilton subgraph G=(V, E) of G such that the addition of an edge e E-Edestroys the planarity, unless we delete an edge from Ehaving no less weight than e. The time complexities of the algorithms are O(n+m), O(m^3/2) and O(m^5/3), respectively, where n(resp., m) is the number of vertices (resp., edges) of the Hamilton graph. These algorithms are applicable to the Topological Via Minimization problem.

• Publication: IEICE TRANSACTIONS on Fundamentals Vol.E74-A No.4 pp.657-664
• Publication Date: 1991/04/25
• Type of Manuscript: Special Section PAPER (Special Issue on Discrete Mathematics and Its Applications)

Authors

Noriya KOBAYASHI
Sumio MASUDA
Toshinobu KASHIWABARA

Keyword