Bounded Degree Conjecture Holds Precisely for c-Crossing-Critical Graphs with c ≤ 12 View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2022-03-14

AUTHORS

Drago Bokal, Zdenĕk Dvořák, Petr Hlinĕný, Jesús Leaños, Bojan Mohar, Tilo Wiedera

ABSTRACT

We study c-crossing-critical graphs, which are the minimal graphs that require at least c edge-crossings when drawn in the plane. For every fixed pair of integers with c ≥ 13 and d ≥ 1, we give first explicit constructions of c-crossing-critical graphs containing arbitrarily many vertices of degree greater than d. We also show that such unbounded degree constructions do not exist for c ≤ 12, precisely, that there exists a constant D such that every c-crossing-critical graph with c ≤ 12 has maximum degree at most D. Hence, the bounded maximum degree conjecture of c-crossing-critical graphs, which was generally disproved in 2010 by Dvořák and Mohar (without an explicit construction), holds true, surprisingly, exactly for the values c ≤ 12.1 More... »

PAGES

1-28

References to SciGraph publications

  • 2021-08-24. On 13-Crossing-Critical Graphs with Arbitrarily Large Degrees in EXTENDED ABSTRACTS EUROCOMB 2021
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00493-021-4285-3

    DOI

    http://dx.doi.org/10.1007/s00493-021-4285-3

    DIMENSIONS

    https://app.dimensions.ai/details/publication/pub.1146254932


    Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
    Incoming Citations Browse incoming citations for this publication using opencitations.net

    JSON-LD is the canonical representation for SciGraph data.

    TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "about": [
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Mathematical Sciences", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Pure Mathematics", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Department of Mathematics and Computer Science, University of Maribor, Maribor, Slovenia", 
              "id": "http://www.grid.ac/institutes/grid.8647.d", 
              "name": [
                "Department of Mathematics and Computer Science, University of Maribor, Maribor, Slovenia"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Bokal", 
            "givenName": "Drago", 
            "id": "sg:person.014125475076.14", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014125475076.14"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Computer Science Institute, Charles University, Prague, Czech Republic", 
              "id": "http://www.grid.ac/institutes/grid.4491.8", 
              "name": [
                "Computer Science Institute, Charles University, Prague, Czech Republic"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Dvo\u0159\u00e1k", 
            "givenName": "Zden\u0115k", 
            "id": "sg:person.016201177201.22", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016201177201.22"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Faculty of Informatics, Masaryk University, Brno, Czech Republic", 
              "id": "http://www.grid.ac/institutes/grid.10267.32", 
              "name": [
                "Faculty of Informatics, Masaryk University, Brno, Czech Republic"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Hlin\u0115n\u00fd", 
            "givenName": "Petr", 
            "id": "sg:person.07741067633.11", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07741067633.11"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Academic Unit of Mathematics, Autonomous University of Zacatecas, Zacatecas, Mexico", 
              "id": "http://www.grid.ac/institutes/grid.412865.c", 
              "name": [
                "Academic Unit of Mathematics, Autonomous University of Zacatecas, Zacatecas, Mexico"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Lea\u00f1os", 
            "givenName": "Jes\u00fas", 
            "id": "sg:person.011164414023.43", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011164414023.43"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Institute of Mathematics Physics, and Mechanics, Ljubljana, Slovenia", 
              "id": "http://www.grid.ac/institutes/grid.457169.8", 
              "name": [
                "Department of Mathematics, Simon Fraser University, Burnaby, BC, Canada", 
                "Institute of Mathematics Physics, and Mechanics, Ljubljana, Slovenia"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Mohar", 
            "givenName": "Bojan", 
            "id": "sg:person.014537342061.66", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014537342061.66"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Theoretical Computer Science, Osnabr\u00fcck University, Osnabr\u00fcck, Germany", 
              "id": "http://www.grid.ac/institutes/grid.10854.38", 
              "name": [
                "Theoretical Computer Science, Osnabr\u00fcck University, Osnabr\u00fcck, Germany"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Wiedera", 
            "givenName": "Tilo", 
            "id": "sg:person.012546434467.49", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012546434467.49"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/978-3-030-83823-2_9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1140591339", 
              "https://doi.org/10.1007/978-3-030-83823-2_9"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2022-03-14", 
        "datePublishedReg": "2022-03-14", 
        "description": "We study c-crossing-critical graphs, which are the minimal graphs that require at least c edge-crossings when drawn in the plane. For every fixed pair of integers with c \u2265 13 and d \u2265 1, we give first explicit constructions of c-crossing-critical graphs containing arbitrarily many vertices of degree greater than d. We also show that such unbounded degree constructions do not exist for c \u2264 12, precisely, that there exists a constant D such that every c-crossing-critical graph with c \u2264 12 has maximum degree at most D. Hence, the bounded maximum degree conjecture of c-crossing-critical graphs, which was generally disproved in 2010 by Dvo\u0159\u00e1k and Mohar (without an explicit construction), holds true, surprisingly, exactly for the values c \u2264 12.1", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s00493-021-4285-3", 
        "isAccessibleForFree": true, 
        "isPartOf": [
          {
            "id": "sg:journal.1136493", 
            "issn": [
              "0209-9683", 
              "1439-6912"
            ], 
            "name": "Combinatorica", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }
        ], 
        "keywords": [
          "minimal graphs", 
          "pair of integers", 
          "first explicit construction", 
          "explicit construction", 
          "vertices of degree", 
          "degree conjecture", 
          "graph", 
          "maximum degree", 
          "conjecture", 
          "value c", 
          "degree constructions", 
          "Mohar", 
          "integers", 
          "vertices", 
          "plane", 
          "construction", 
          "D. Hence", 
          "Dvo\u0159\u00e1k", 
          "pairs", 
          "degree", 
          "Hence"
        ], 
        "name": "Bounded Degree Conjecture Holds Precisely for c-Crossing-Critical Graphs with c \u2264 12", 
        "pagination": "1-28", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1146254932"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00493-021-4285-3"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00493-021-4285-3", 
          "https://app.dimensions.ai/details/publication/pub.1146254932"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-09-02T16:08", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20220902/entities/gbq_results/article/article_949.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s00493-021-4285-3"
      }
    ]
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    HOW TO GET THIS DATA PROGRAMMATICALLY:

    JSON-LD is a popular format for linked data which is fully compatible with JSON.

    curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s00493-021-4285-3'

    N-Triples is a line-based linked data format ideal for batch operations.

    curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s00493-021-4285-3'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00493-021-4285-3'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00493-021-4285-3'


     

    This table displays all metadata directly associated to this object as RDF triples.

    127 TRIPLES      21 PREDICATES      44 URIs      35 LITERALS      4 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00493-021-4285-3 schema:about anzsrc-for:01
    2 anzsrc-for:0101
    3 schema:author Na9628b8470934c1f818f2b0acecbf2e7
    4 schema:citation sg:pub.10.1007/978-3-030-83823-2_9
    5 schema:datePublished 2022-03-14
    6 schema:datePublishedReg 2022-03-14
    7 schema:description We study c-crossing-critical graphs, which are the minimal graphs that require at least c edge-crossings when drawn in the plane. For every fixed pair of integers with c ≥ 13 and d ≥ 1, we give first explicit constructions of c-crossing-critical graphs containing arbitrarily many vertices of degree greater than d. We also show that such unbounded degree constructions do not exist for c ≤ 12, precisely, that there exists a constant D such that every c-crossing-critical graph with c ≤ 12 has maximum degree at most D. Hence, the bounded maximum degree conjecture of c-crossing-critical graphs, which was generally disproved in 2010 by Dvořák and Mohar (without an explicit construction), holds true, surprisingly, exactly for the values c ≤ 12.1
    8 schema:genre article
    9 schema:isAccessibleForFree true
    10 schema:isPartOf sg:journal.1136493
    11 schema:keywords D. Hence
    12 Dvořák
    13 Hence
    14 Mohar
    15 conjecture
    16 construction
    17 degree
    18 degree conjecture
    19 degree constructions
    20 explicit construction
    21 first explicit construction
    22 graph
    23 integers
    24 maximum degree
    25 minimal graphs
    26 pair of integers
    27 pairs
    28 plane
    29 value c
    30 vertices
    31 vertices of degree
    32 schema:name Bounded Degree Conjecture Holds Precisely for c-Crossing-Critical Graphs with c ≤ 12
    33 schema:pagination 1-28
    34 schema:productId N44908f59dd1240ce99406e30d04cf757
    35 Nb847cd085e094bfdb3d0414ef3ce037b
    36 schema:sameAs https://app.dimensions.ai/details/publication/pub.1146254932
    37 https://doi.org/10.1007/s00493-021-4285-3
    38 schema:sdDatePublished 2022-09-02T16:08
    39 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    40 schema:sdPublisher N1d0efe52e2d6461eb9c4d939c52d47fb
    41 schema:url https://doi.org/10.1007/s00493-021-4285-3
    42 sgo:license sg:explorer/license/
    43 sgo:sdDataset articles
    44 rdf:type schema:ScholarlyArticle
    45 N1d0efe52e2d6461eb9c4d939c52d47fb schema:name Springer Nature - SN SciGraph project
    46 rdf:type schema:Organization
    47 N2d3d3953f0fd4a539fd9c401dab69ba8 rdf:first sg:person.012546434467.49
    48 rdf:rest rdf:nil
    49 N44908f59dd1240ce99406e30d04cf757 schema:name doi
    50 schema:value 10.1007/s00493-021-4285-3
    51 rdf:type schema:PropertyValue
    52 N47632a6ce5f0421689fc75f7d86862af rdf:first sg:person.011164414023.43
    53 rdf:rest Nfcee2d34059d4c7686c55302c4ffb261
    54 N5e6fac8b4f4a46079794f94973af7906 rdf:first sg:person.07741067633.11
    55 rdf:rest N47632a6ce5f0421689fc75f7d86862af
    56 Na7f7467f6b6343c0a21028112262c1b7 rdf:first sg:person.016201177201.22
    57 rdf:rest N5e6fac8b4f4a46079794f94973af7906
    58 Na9628b8470934c1f818f2b0acecbf2e7 rdf:first sg:person.014125475076.14
    59 rdf:rest Na7f7467f6b6343c0a21028112262c1b7
    60 Nb847cd085e094bfdb3d0414ef3ce037b schema:name dimensions_id
    61 schema:value pub.1146254932
    62 rdf:type schema:PropertyValue
    63 Nfcee2d34059d4c7686c55302c4ffb261 rdf:first sg:person.014537342061.66
    64 rdf:rest N2d3d3953f0fd4a539fd9c401dab69ba8
    65 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    66 schema:name Mathematical Sciences
    67 rdf:type schema:DefinedTerm
    68 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
    69 schema:name Pure Mathematics
    70 rdf:type schema:DefinedTerm
    71 sg:journal.1136493 schema:issn 0209-9683
    72 1439-6912
    73 schema:name Combinatorica
    74 schema:publisher Springer Nature
    75 rdf:type schema:Periodical
    76 sg:person.011164414023.43 schema:affiliation grid-institutes:grid.412865.c
    77 schema:familyName Leaños
    78 schema:givenName Jesús
    79 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011164414023.43
    80 rdf:type schema:Person
    81 sg:person.012546434467.49 schema:affiliation grid-institutes:grid.10854.38
    82 schema:familyName Wiedera
    83 schema:givenName Tilo
    84 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012546434467.49
    85 rdf:type schema:Person
    86 sg:person.014125475076.14 schema:affiliation grid-institutes:grid.8647.d
    87 schema:familyName Bokal
    88 schema:givenName Drago
    89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014125475076.14
    90 rdf:type schema:Person
    91 sg:person.014537342061.66 schema:affiliation grid-institutes:grid.457169.8
    92 schema:familyName Mohar
    93 schema:givenName Bojan
    94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014537342061.66
    95 rdf:type schema:Person
    96 sg:person.016201177201.22 schema:affiliation grid-institutes:grid.4491.8
    97 schema:familyName Dvořák
    98 schema:givenName Zdenĕk
    99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016201177201.22
    100 rdf:type schema:Person
    101 sg:person.07741067633.11 schema:affiliation grid-institutes:grid.10267.32
    102 schema:familyName Hlinĕný
    103 schema:givenName Petr
    104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07741067633.11
    105 rdf:type schema:Person
    106 sg:pub.10.1007/978-3-030-83823-2_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1140591339
    107 https://doi.org/10.1007/978-3-030-83823-2_9
    108 rdf:type schema:CreativeWork
    109 grid-institutes:grid.10267.32 schema:alternateName Faculty of Informatics, Masaryk University, Brno, Czech Republic
    110 schema:name Faculty of Informatics, Masaryk University, Brno, Czech Republic
    111 rdf:type schema:Organization
    112 grid-institutes:grid.10854.38 schema:alternateName Theoretical Computer Science, Osnabrück University, Osnabrück, Germany
    113 schema:name Theoretical Computer Science, Osnabrück University, Osnabrück, Germany
    114 rdf:type schema:Organization
    115 grid-institutes:grid.412865.c schema:alternateName Academic Unit of Mathematics, Autonomous University of Zacatecas, Zacatecas, Mexico
    116 schema:name Academic Unit of Mathematics, Autonomous University of Zacatecas, Zacatecas, Mexico
    117 rdf:type schema:Organization
    118 grid-institutes:grid.4491.8 schema:alternateName Computer Science Institute, Charles University, Prague, Czech Republic
    119 schema:name Computer Science Institute, Charles University, Prague, Czech Republic
    120 rdf:type schema:Organization
    121 grid-institutes:grid.457169.8 schema:alternateName Institute of Mathematics Physics, and Mechanics, Ljubljana, Slovenia
    122 schema:name Department of Mathematics, Simon Fraser University, Burnaby, BC, Canada
    123 Institute of Mathematics Physics, and Mechanics, Ljubljana, Slovenia
    124 rdf:type schema:Organization
    125 grid-institutes:grid.8647.d schema:alternateName Department of Mathematics and Computer Science, University of Maribor, Maribor, Slovenia
    126 schema:name Department of Mathematics and Computer Science, University of Maribor, Maribor, Slovenia
    127 rdf:type schema:Organization
     




    Preview window. Press ESC to close (or click here)


    ...