Recognizing Planar Strict Quasi-Parity Graphs |
| |
| Authors: | Cláudia Linhares Sales Frédéric Maffray Bruce Reed |
| |
| Institution: | (1) Universidade Federal do Ceará, Rua Deputado Moreira da Rocha 380, 601, Meireles, Fortaleza-CE, CEP 60160-060, Brazil. e-mail: linhares@lia.ufc.br, BR;(2) CNRS, Laboratoire Leibniz-IMAG, 46 avenue Félix Viallet, 38031 Grenoble Cedex, France, FR;(3) CNRS, Equipe Combinatoire, Université Pierre et Marie Curie, 4 place Jussieu, 75005 Paris, France, FR |
| |
| Abstract: | A graph is a strict-quasi parity (SQP) graph if every induced subgraph that is not a clique contains a pair of vertices with
no odd chordless path between them (an “even pair”). We present an O(n
3) algorithm for recognizing planar strict quasi-parity graphs, based on Wen-Lian Hsu's decomposition of planar (perfect) graphs
and on the (non-algorithmic) characterization of planar minimal non-SQP graphs given in 9].
Received: September 21, 1998 Final version received: May 9, 2000 |
| |
| Keywords: | , ,Perfect graphs, Even pairs, Planar graphs, Strict quasi-parity graphs, Recognition |
| 本文献已被 SpringerLink 等数据库收录！ |
|
