Extending planar graph algorithms to K 3,3-free graphs

Samir Khuller

doi:10.1007/3-540-50517-2_71

Extending planar graph algorithms to K _3,3-free graphs

Samir Khuller^*

^*Corresponding author for this work

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

1 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 K_3,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 K_3,3-free graphs are five colorable (this bound is tight).

Original language	English (US)
Title of host publication	Foundations of Software Technology and Theoretical Computer Science - 8th Conference, Proceedings
Editors	Kesav V. Nori, Sanjeev Kumar
Publisher	Springer Verlag
Pages	67-79
Number of pages	13
ISBN (Print)	9783540505174
DOIs	https://doi.org/10.1007/3-540-50517-2_71
State	Published - 1988
Event	8th International Conference on Foundations of Software Technology and Theoretical Computer Science, FST and TCS 1988 - Pune, India Duration: Dec 21 1988 → Dec 23 1988

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	338 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	8th International Conference on Foundations of Software Technology and Theoretical Computer Science, FST and TCS 1988
Country/Territory	India
City	Pune
Period	12/21/88 → 12/23/88

Funding

*supported by NSF grant DCR 85 52938 and PYI matching funds from AT&T Bell Labs.

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-50517-2_71

Cite this

Khuller, S. (1988). Extending planar graph algorithms to K _3,3-free graphs. In K. V. Nori, & S. Kumar (Eds.), Foundations of Software Technology and Theoretical Computer Science - 8th Conference, Proceedings (pp. 67-79). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 338 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-50517-2_71

Khuller, Samir. / Extending planar graph algorithms to K _3,3-free graphs. Foundations of Software Technology and Theoretical Computer Science - 8th Conference, Proceedings. editor / Kesav V. Nori ; Sanjeev Kumar. Springer Verlag, 1988. pp. 67-79 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{a2fd2c3edaa9496d9155af8ae3e5fd3a,

title = "Extending planar graph algorithms to K 3,3-free graphs",

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).",

author = "Samir Khuller",

note = "Publisher Copyright: {\textcopyright} 1988, Springer-Verlag.; 8th International Conference on Foundations of Software Technology and Theoretical Computer Science, FST and TCS 1988 ; Conference date: 21-12-1988 Through 23-12-1988",

year = "1988",

doi = "10.1007/3-540-50517-2_71",

language = "English (US)",

isbn = "9783540505174",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "67--79",

editor = "Nori, {Kesav V.} and Sanjeev Kumar",

booktitle = "Foundations of Software Technology and Theoretical Computer Science - 8th Conference, Proceedings",

}

Khuller, S 1988, Extending planar graph algorithms to K _3,3-free graphs. in KV Nori & S Kumar (eds), Foundations of Software Technology and Theoretical Computer Science - 8th Conference, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 338 LNCS, Springer Verlag, pp. 67-79, 8th International Conference on Foundations of Software Technology and Theoretical Computer Science, FST and TCS 1988, Pune, India, 12/21/88. https://doi.org/10.1007/3-540-50517-2_71

Extending planar graph algorithms to K _3,3-free graphs. / Khuller, Samir.
Foundations of Software Technology and Theoretical Computer Science - 8th Conference, Proceedings. ed. / Kesav V. Nori; Sanjeev Kumar. Springer Verlag, 1988. p. 67-79 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 338 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Extending planar graph algorithms to K 3,3-free graphs

AU - Khuller, Samir

PY - 1988

Y1 - 1988

N2 - 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).

AB - 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).

UR - http://www.scopus.com/inward/record.url?scp=85023429597&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85023429597&partnerID=8YFLogxK

U2 - 10.1007/3-540-50517-2_71

DO - 10.1007/3-540-50517-2_71

M3 - Conference contribution

AN - SCOPUS:85023429597

SN - 9783540505174

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 67

EP - 79

BT - Foundations of Software Technology and Theoretical Computer Science - 8th Conference, Proceedings

A2 - Nori, Kesav V.

A2 - Kumar, Sanjeev

PB - Springer Verlag

T2 - 8th International Conference on Foundations of Software Technology and Theoretical Computer Science, FST and TCS 1988

Y2 - 21 December 1988 through 23 December 1988

ER -

Khuller S. Extending planar graph algorithms to K _3,3-free graphs. In Nori KV, Kumar S, editors, Foundations of Software Technology and Theoretical Computer Science - 8th Conference, Proceedings. Springer Verlag. 1988. p. 67-79. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-50517-2_71