### Abstract

Given a graph G and two pairs of vertices s_{1}, t_{1} and s_{2}, t_{2}, the two disjoint paths problem asks for vertex-disjoint paths connecting s_{i} with t_{i}, i = 1, 2. A fast parallel (NC) algorithm is given for this problem, which has applications in certain routing situations. If G is nonplanar, an algorithm that finds a Kuratowski homeomorph in G (i.e., a subgraph homeomorphic to K_{3,3} or K_{5}) is given. This complements the known NC planarity algorithms, which give a planar embedding in the positive case; the algorithm here provides a certificate of nonplanarity in the negative case. Both algorithms are processor efficient; in each case, the processor-time product is within a polylogarithmic factor of the best known sequential algorithm.

Original language | English (US) |
---|---|

Title of host publication | Annual Symposium on Foundations of Computer Science (Proceedings) |

Publisher | Publ by IEEE |

Pages | 300-305 |

Number of pages | 6 |

ISBN (Print) | 0818619821, 9780818619823 |

DOIs | |

State | Published - 1989 |

Event | 30th Annual Symposium on Foundations of Computer Science - Research Triangle Park, NC, USA Duration: Oct 30 1989 → Nov 1 1989 |

### Publication series

Name | Annual Symposium on Foundations of Computer Science (Proceedings) |
---|---|

ISSN (Print) | 0272-5428 |

### Conference

Conference | 30th Annual Symposium on Foundations of Computer Science |
---|---|

City | Research Triangle Park, NC, USA |

Period | 10/30/89 → 11/1/89 |

### ASJC Scopus subject areas

- Hardware and Architecture

## Fingerprint Dive into the research topics of 'Processor efficient parallel algorithms for the two disjoint paths problem, and for finding a Kuratowski homeomorph'. Together they form a unique fingerprint.

## Cite this

*Annual Symposium on Foundations of Computer Science (Proceedings)*(pp. 300-305). (Annual Symposium on Foundations of Computer Science (Proceedings)). Publ by IEEE. https://doi.org/10.1109/sfcs.1989.63494