Akademska digitalna zbirka SLovenije - logo
(UL)
  • Universal obstructions for embedding extension problems
    Mohar, Bojan, 1956-
    Let ▫$K$▫ be an induced non-separating subgraph of a graph ▫$G$▫, and let ▫$B$▫ be the bridge of ▫$K$▫ in ▫$G$▫. Obstructions for extending a given 2-cell embedding of ▫$K$▫ to an embedding of ▫$G$▫ ... in the same surface are considered. It is shown that it is possible to find a nice obstruction which means that it is small up to a small number of almost disjoint millipedes. Moreover, ▫$B$▫ contains a nice subgraph ▫$\tilde{b}$▫ with the following properties. If ▫$K$▫ is 2-cell embedded in some surface and ▫$F$▫ is a face of ▫$K$▫, then ▫$\tilde{B}$▫ admits exactly the same types of embeddings in ▫$F$▫ as ▫$B$▫. A linear time algorithm to construct such a universal obstruction ▫$\tilde{B}$▫ is presented. At the same time, for every type of embeddings of ▫$\tilde{B}$▫, an embedding of ▫$B$▫ of the same type is determined.
    Vir: The Australasian journal of combinatorics. - ISSN 1034-4942 (Vol. 36, 2006, str. 39-68)
    Vrsta gradiva - članek, sestavni del
    Leto - 2006
    Jezik - angleški
    COBISS.SI-ID - 14132057

Vnos na polico