For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Algorithms to Obtain a Maximal Planar Hamilton Subgraph
Noriya KOBAYASHI Sumio MASUDA Toshinobu KASHIWABARA
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1991/04/25
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Issue on Discrete Mathematics and Its Applications)
Full Text: PDF>>
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(m3/2) and O(m5/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.