๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

A linear-time algorithm for four-partitioning four-connected planar graphs

โœ Scribed by Shin-ichi Nakano; Md.Saidur Rahman; Takao Nishizeki

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
765 KB
Volume
62
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

โœฆ Synopsis

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 and a "canonical 4-ordering" known in the area of graph drawings. @ 1997 Elsevier Science B.V.

๐Ÿ“œ SIMILAR VOLUMES

A linear time recognition algorithm for
A linear time recognition algorithm for proper interval graphs
โœ B.S. Panda; Sajal K. Das ๐Ÿ“‚ Article ๐Ÿ“… 2003 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 128 KB

We propose a linear time recognition algorithm for proper interval graphs. The algorithm is based on certain ordering of vertices, called bicompatible elimination ordering (BCO). Given a BCO of a biconnected proper interval graph G, we also propose a linear time algorithm to construct a Hamiltonian