VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
  • Minimal obstructions for 1-immersions and hardness of 1-planarity testing
    Korzhik, Vladimir P. ; Mohar, Bojan, 1956-
    A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by no more than one other edge. A non-1-planar graph ▫$G$▫ is minimal if the graph ▫$G-e$▫ is 1-planar for every edge ... ▫$e$▫ of $G$. We construct two infinite families of minimal non-1-planar graphs and show that for every integer ▫$n \geq 63$▫, there are at least ▫$2^{(n-54)/4}$▫ nonisomorphic minimal non-1-planar graphs of order ▫$n$▫. It is also proved that testing 1-planarity is NP-complete.
    Vir: Journal of graph theory. - ISSN 0364-9024 (Vol. 72, no. 1, 2013, str. 30-71)
    Vrsta gradiva - članek, sestavni del
    Leto - 2013
    Jezik - angleški
    COBISS.SI-ID - 16557401

    Povezava(-e):

    http://dx.doi.org/10.1002/jgt.21630

vir: Journal of graph theory. - ISSN 0364-9024 (Vol. 72, no. 1, 2013, str. 30-71)
loading ...
loading ...
loading ...

Vnos na polico