Extending planar graph algorithms to \(K_{3,3}\)-free graphs

DOI10.1016/0890-5401(90)90031-CzbMath0689.68091MaRDI QIDQ582121

Samir Khuller

Publication date: 1990

Published in: Information and Computation (Search for Journal in Brave)

zbMATH Keywords

graph coloringparallel algorithmsCRCW PRAMdepth first searchmaximal independent

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Related Items

A parallel algorithm for finding a triconnected component separator with an application, Tight upper bound on the number of edges in a bipartite \(K_{3,3}\)-free or \(K_{5}\)-free graph with an application.

Cites Work

• An approach to the subgraph homeomorphism problem
• Finding small simple cycle separators for 2-connected planar graphs
• A random NC algorithm for depth first search
• NC algorithms for computing the number of perfect matchings in \(K_{3,3}\)-free graphs and related problems
• Every planar map is four colorable. I: Discharging
• Parallel Algorithms for Depth-First Searches I. Planar Graphs
• A Nearly Optimal Parallel Algorithm for Constructing Depth First Spanning Trees in Planar Graphs
• Efficient Planarity Testing
• Dividing a Graph into Triconnected Components
• A note on primitive skew curves
• Unnamed Item
• Unnamed Item