Not all planar diagraphs have small cycle separators

Ming Yang Kao; Fang Wan

doi:10.1016/0020-0190(92)90189-3

Not all planar diagraphs have small cycle separators

Ming Yang Kao^*, Fang Wan

^*Corresponding author for this work

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

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 language	English (US)
Pages (from-to)	79-83
Number of pages	5
Journal	Information Processing Letters
Volume	44
Issue number	2
DOIs	https://doi.org/10.1016/0020-0190(92)90189-3
State	Published - Nov 19 1992

Keywords

Combinatorial problems
cycle separators
path separators
planar directed graphs

ASJC Scopus subject areas

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Access to Document

10.1016/0020-0190(92)90189-3

Cite this

@article{754aba6e1cb44e29a9d9067798472aef,

title = "Not all planar diagraphs have small cycle separators",

abstract = "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.",

keywords = "Combinatorial problems, cycle separators, path separators, planar directed graphs",

author = "Kao, {Ming Yang} and Fang Wan",

note = "Funding Information: Correspondence to: M.-Y. Kao, Department of Computer Scienl:e, Duke University, Durham, NC 27706, USA. * Supported in part by NSF Grant CCR-8909323.",

year = "1992",

month = nov,

day = "19",

doi = "10.1016/0020-0190(92)90189-3",

language = "English (US)",

volume = "44",

pages = "79--83",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "2",

}

TY - JOUR

T1 - Not all planar diagraphs have small cycle separators

AU - Kao, Ming Yang

AU - Wan, Fang

N1 - Funding Information: Correspondence to: M.-Y. Kao, Department of Computer Scienl:e, Duke University, Durham, NC 27706, USA. * Supported in part by NSF Grant CCR-8909323.

PY - 1992/11/19

Y1 - 1992/11/19

N2 - 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.

AB - 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.

KW - Combinatorial problems

KW - cycle separators

KW - path separators

KW - planar directed graphs

UR - http://www.scopus.com/inward/record.url?scp=28144434735&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=28144434735&partnerID=8YFLogxK

U2 - 10.1016/0020-0190(92)90189-3

DO - 10.1016/0020-0190(92)90189-3

M3 - Article

AN - SCOPUS:28144434735

SN - 0020-0190

VL - 44

SP - 79

EP - 83

JO - Information Processing Letters

JF - Information Processing Letters

IS - 2

ER -

Not all planar diagraphs have small cycle separators

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this