Extending planar graph algorithms to K3,3-free graphs

Samir Khuller*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

Abstract

For several problems, restricting attention to special classes of graphs has yielded better algorithms. In particular, restricting to planar graphs yields efficient parallel algorithms for several graph problems. In this paper we extend these algorithms to K3,3-free graphs, showing that the restriction of planarity is not important. The three problems dealt with are: graph coloring, depth first search, and maximal independent sets. As a corollary we show that K3,3-free graphs are five colorable (this bound is tight).

Original languageEnglish (US)
Pages (from-to)13-25
Number of pages13
JournalInformation and Computation
Volume84
Issue number1
DOIs
StatePublished - Jan 1990

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Extending planar graph algorithms to K<sub>3,3</sub>-free graphs'. Together they form a unique fingerprint.

Cite this