Extending planar graph algorithms to \(K_{3,3}\)-free graphs
From MaRDI portal
Publication:582121
DOI10.1016/0890-5401(90)90031-CzbMath0689.68091MaRDI QIDQ582121
Publication date: 1990
Published in: Information and Computation (Search for Journal in Brave)
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