Computing an st-numbering

Shimon Even, Robert Endre Tarjan

Research output: Contribution to journalArticlepeer-review

186 Scopus citations

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 languageEnglish (US)
Pages (from-to)339-344
Number of pages6
JournalTheoretical Computer Science
Volume2
Issue number3
DOIs
StatePublished - Sep 1976
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Computing an st-numbering'. Together they form a unique fingerprint.

Cite this