Not all planar diagraphs have small cycle separators

Ming Yang Kao*, Fang Wan

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


Kao recently proved that all general directed graphs have directed cycle separators of any size. In contrast, Miller proved that planar undirected graphs with n vertices and maximum face size d have O( dn)-size undirected cycle separators. Therefore it is important to investigate whether a planar directed graph has a small-size directed cycle separator. This paper shows that certain important classes of planar directed graphs have no sublinear-size directed cycle separators.

Original languageEnglish (US)
Pages (from-to)79-83
Number of pages5
JournalInformation Processing Letters
Issue number2
StatePublished - Nov 19 1992


  • Combinatorial problems
  • cycle separators
  • path separators
  • planar directed graphs

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications


Dive into the research topics of 'Not all planar diagraphs have small cycle separators'. Together they form a unique fingerprint.

Cite this