id: 06033518
dt: j
an: 06033518
au: Kawarabayashi, Ken-Ichi; Kobayashi, Yusuke
ti: A linear time algorithm for the induced disjoint paths problem in planar
    graphs.
so: J. Comput. Syst. Sci. 78, No. 2, 670-680 (2012).
py: 2012
pu: Elsevier Science (Academic Press), San Diego, CA
la: EN
cc: 
ut: disjoint paths; induced subgraph; planar graph; linear time algorithm
ci: Zbl 0791.05092; Zbl 0794.05121
li: doi:10.1016/j.jcss.2011.10.004
ab: Summary: In this paper, we consider a problem which we call the induced
    disjoint paths problem (IDPP) for planar graphs. We are given a planar
    graph G and a collection of vertex pairs $\{(s_{1},t_{1}),\ldots
    ,(s_k,t_k)\}$. The objective is to find k paths $P_{1},\ldots ,P_k$
    such that $P_i$ is a path from $s_i$ to $t_i$ and $P_i$ and $P_j$ have
    neither common vertices nor adjacent vertices for any distinct $i,j$.
    This problem setting is a generalization of the disjoint paths problem,
    since if we subdivide each edge, then desired disjoint paths would be
    induced disjoint paths. The problem is motivated by not only the
    disjoint paths problem but also the recognition of an induced subgraph.
    The latter has been developed in recent years, and this is actually
    connected to the Strong Perfect Graph Theorem, and the recognition of
    the perfect graphs. Our main result in this paper is to give a linear
    time algorithm for the IDPP for planar graphs. This generalizes the
    result by {\it B. A. Reed}, {\it N. Robertson}, {\it A. Schrijver} and
    {\it P. D. Seymour} [Contemp. Math. 147, 295‒301 (1993; Zbl
    0791.05092)]. This also gives a polynomial time algorithm to find an
    induced circuit through given $k$ vertices in planar graphs if one
    exists when $k$ is fixed. The case $k=2$ was previously proved by {\it
    C. McDiarmid}, {\it B. Reed}, {\it A. Schrijver} and {\it B. Shepherd}
    [J. Comb. Theory, Ser. B 60, No. 2, 169‒176 (1994; Zbl 0794.05121)].
rv: