𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A linear algorithm for finding Hamiltonian cycles in 4-connected maximal planar graphs

✍ Scribed by Takao Asano; Shunji Kikuchi; Nobuji Saito

Publisher
Elsevier Science
Year
1984
Tongue
English
Weight
901 KB
Volume
7
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

On the number of hamiltonian cycles in a
On the number of hamiltonian cycles in a maximal planar graph
✍ S. L. Hakimi; E. F. Schmeichel; C. Thomassen πŸ“‚ Article πŸ“… 1979 πŸ› John Wiley and Sons 🌐 English βš– 243 KB πŸ‘ 2 views

## Abstract We consider the problem of the minimum number of Hamiltonian cycles that could be present in a Hamiltonian maximal planar graph on __p__ vertices. In particular, we construct a __p__‐vertex maximal planar graph containing exactly four Hamiltonian cycles for every __p__ β‰₯ 12. We also pro

A linear-time algorithm for four-partiti
A linear-time algorithm for four-partitioning four-connected planar graphs
✍ Shin-ichi Nakano; Md.Saidur Rahman; Takao Nishizeki πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 765 KB

In this paper we give a simple linear-time algorithm to find such a partition if G is a 4-connected planar graph and ~1. ~2. 143 and u4 are located on the same face of a plane embedding of G. Our algorithm is based on a "4canonical decomposition" of G, which is a generalization of an St-numbering an