Akademska digitalna zbirka SLovenije - logo
(UL)
  • Linkless and flat embeddings in 3-space
    Kawarabayashi, Ken-ichi ; Kreutzer, Stephan ; Mohar, Bojan, 1956-
    We consider piecewise linear embeddings of graphs in 3-space ▫$\mathbb R^{3}$▫. Such an embedding is linkless if every pair of disjoint cycles forms a trivial link (in the sense of knot theory). ... Robertson, Seymour and Thomas [J. Comb. Theory, Ser. B 64, No. 2, 185--227 (1995)] showed that a graph has a linkless embedding in $\mathbb ▫R^{3}$▫ if and only if it does not contain as a minor any of seven graphs in Petersen's family (graphs obtained from ▫$K _{6}$▫ by a series of ▫$Y\Delta $▫ and ▫$\Delta Y$▫ operations). They also showed that a graph is linklessly embeddable in ▫$\mathbb R^{3}$▫ if and only if it admits a flat embedding into ▫$\mathbb R^{3}$▫, i.e. an embedding such that for every cycle ▫$C$▫ of ▫$G$▫ there exists a closed 2-disk ▫$D\subseteq \mathbb R^{3}$▫ with ▫$D\cap G = \partial D = C$▫. Clearly, every flat embedding is linkless, but the converse is not true. We consider the following algorithmic problem associated with embeddings in ▫$\mathbb R^{3}$▫: Flat Embedding: For a given graph ▫$G$▫, either detect one of Petersen's family graphs as a minor in ▫$G$▫, or return a flat (and hence linkless) embedding of ▫$G$▫ in ▫$\mathbb R^{3}$▫. The first outcome is a certificate that ▫$G$▫ has no linkless and no flat embeddings. Our main result is to give an ▫$O(n ^{2})$▫ algorithm for this problem. While there is a known polynomial-time algorithm for constructing linkless embeddings [van der Holst in J. Comb. Theory, Ser. B 99, No. 2, 512--530 (2009)], this is the first polynomial-time algorithm for constructing flat embeddings in 3-space. This settles a problem proposed by Lovász (http://www.cs.elte.hu/~lovasz/klee.ppt, 2000).
    Vir: Discrete & computational geometry. - ISSN 0179-5376 (Vol. 47, iss. 4, 2012, str. 731-755)
    Vrsta gradiva - članek, sestavni del ; neleposlovje za odrasle
    Leto - 2012
    Jezik - angleški
    COBISS.SI-ID - 17769561

    Povezava(-e):

    http://dx.doi.org/10.1007/s00454-012-9413-9

vir: Discrete & computational geometry. - ISSN 0179-5376 (Vol. 47, iss. 4, 2012, str. 731-755)

loading ...
loading ...
loading ...

Vnos na polico