Odd cyclic surface separators in planar graphs

Petr A. Golovach; Marcin Kamiński; Dimitrios M. Thilikos

Odd cyclic surface separators in planar graphs

Petr A. Golovach, Marcin Kamiński, Dimitrios M. Thilikos

Computer Science

Research output: Contribution to conference › Paper › peer-review

Abstract

Given a plane graph G and two vertices s and t in G, an s-t surface separator is a closed curve C such that s belongs to the other region of R ² \ C than t. A cycle C is called a cyclic surface separator if C is an s-t surface separator, and an odd cyclic surface separator if C is an odd cycle. We consider the problem of finding odd cyclic surface separators in planar graphs and show that the problem can be solved in polynomial time.

Original language	English (US)
Pages	165-167
Number of pages	3
State	Published - 2011
Event	10th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2011 - Frascati, Italy Duration: Jun 14 2011 → Jun 16 2011

Conference

Conference	10th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2011
Country/Territory	Italy
City	Frascati
Period	6/14/11 → 6/16/11

Keywords

Irrelevant vertex
Odd cycles
Planar graphs

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics

Cite this

@conference{df47506959174b679d44947cf8e28fbc,

title = "Odd cyclic surface separators in planar graphs",

abstract = "Given a plane graph G and two vertices s and t in G, an s-t surface separator is a closed curve C such that s belongs to the other region of R 2 \ C than t. A cycle C is called a cyclic surface separator if C is an s-t surface separator, and an odd cyclic surface separator if C is an odd cycle. We consider the problem of finding odd cyclic surface separators in planar graphs and show that the problem can be solved in polynomial time.",

keywords = "Irrelevant vertex, Odd cycles, Planar graphs",

author = "Golovach, {Petr A.} and Marcin Kami{\'n}ski and Thilikos, {Dimitrios M.}",

year = "2011",

language = "English (US)",

pages = "165--167",

note = "10th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2011 ; Conference date: 14-06-2011 Through 16-06-2011",

}

TY - CONF

T1 - Odd cyclic surface separators in planar graphs

AU - Golovach, Petr A.

AU - Kamiński, Marcin

AU - Thilikos, Dimitrios M.

PY - 2011

Y1 - 2011

N2 - Given a plane graph G and two vertices s and t in G, an s-t surface separator is a closed curve C such that s belongs to the other region of R 2 \ C than t. A cycle C is called a cyclic surface separator if C is an s-t surface separator, and an odd cyclic surface separator if C is an odd cycle. We consider the problem of finding odd cyclic surface separators in planar graphs and show that the problem can be solved in polynomial time.

AB - Given a plane graph G and two vertices s and t in G, an s-t surface separator is a closed curve C such that s belongs to the other region of R 2 \ C than t. A cycle C is called a cyclic surface separator if C is an s-t surface separator, and an odd cyclic surface separator if C is an odd cycle. We consider the problem of finding odd cyclic surface separators in planar graphs and show that the problem can be solved in polynomial time.

KW - Irrelevant vertex

KW - Odd cycles

KW - Planar graphs

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

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

M3 - Paper

AN - SCOPUS:84883093198

SP - 165

EP - 167

T2 - 10th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2011

Y2 - 14 June 2011 through 16 June 2011

ER -

Odd cyclic surface separators in planar graphs

Abstract

Conference

Keywords

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this