Akademska digitalna zbirka SLovenije - logo
FMF in IMFM, Matematična knjižnica, Ljubljana (MAKLJ)
  • Oriented matroids and complete-graph embeddings on surfaces
    Bokowski, Jürgen ; Pisanski, Tomaž
    We provide a link between topological graph theory and pseudoline arrangements from the theory of oriented matroids. We investigate and generalize a function ▫$f$▫ that assigns to each simple ... pseudoline arrangement with an even number of elements a pair of complete-graph embeddings on a surface. Each element of the pair keeps the information of the oriented matroid we started with. We call a simple pseudoline arrangement triangular, when the cells in the cell decomposition of the projective plane are 2-colorable and when one color class of cells consists of triangles only. Precisely for triangular pseudoline arrangements, one element of the image pair of ▫$f$▫ is a triangular complete-graph embedding on a surface. We obtain all triangular complete-graph embeddings on surfaces this way, when we extend the definition of triangular complete pseudoline arrangements in a natural way to that of triangular curve arrangements on surfaces in which each pair of curves has a point in common where they cross. Thus Ringel's results on the triangular complete-graph embeddings can be interpreted as results on curve arrangements on surfaces. Furthermore, we establish the relationship between 2-colorable curve arrangements and Petrie dual maps. A data structure, called intersection pattern is provided for the study of curve arrangements on surfaces. Finally we show that an orientable surface of genus ▫$g$▫ admits a complete curve arrangement with at most ▫$2g+1$▫ curves in contrast to the non-orientable surface where the number of curves is not bounded.
    Vir: Journal of combinatorial theory. Series A. - ISSN 0097-3165 (Vol. 114, iss. 1, 2007, str. 1-19)
    Vrsta gradiva - članek, sestavni del
    Leto - 2007
    Jezik - angleški
    COBISS.SI-ID - 14185049

    Povezava(-e):

    http://dx.doi.org/10.1016/j.jcta.2006.06.012

Vnos na polico