## Abstract

Lempel, Even and Cederbaum proved the following result: Given any edge {st} in a biconnected graph G with n vertices, the vertices of G can be numbered from 1 to n so that vertex s receives number 1, vertex t receives number n, and any vertex except s and t is adjacent both to a lower-numbered and to a higher-numbered vertex (we call such a numbering an st-numbering for G). They used this result in an efficient algorithm for planarity-testing. Here we provide a linear-time algorithm for computing an st-numbering for any biconnected graph. This algorithm can be combined with some new results by Booth and Lueker to provide a linear-time implementation of the Lempel-Even-Cederbaum planarity-testing algorithm.

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

Pages (from-to) | 339-344 |

Number of pages | 6 |

Journal | Theoretical Computer Science |

Volume | 2 |

Issue number | 3 |

DOIs | |

State | Published - Sep 1976 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- General Computer Science