All
All

What are you looking for?

All
Projects
Organizations

Quick search

  • Projects supported by TA ČR
  • Excellent projects
  • Projects with the highest public support
  • Current projects

Smart search

  • That is how I find a specific +word
  • That is how I leave the -word out of the results
  • “That is how I can find the whole phrase”

On Degree Properties of Crossing-critical Families of Graphs

Result description

Answering an open question from 2007, we construct infinite k-crossing-critical families of graphs which contain vertices of any prescribed odd degree, for sufficiently large k. From this we derive that, for any set of integers D such that min(D)>=3 and 3,4eD, and for all sufficiently large k there exists a k-crossing-critical family such that the numbers in D are precisely the vertex degrees which occur arbitrarily often in any large enough graph in this family. We also investigate what are the possible average degrees of such crossing-critical families.

Keywords

Crossing numberTile drawingDegree-universalityAverage degreeCrossing-critical graph

The result's identifiers

Alternative languages

  • Result language

    angličtina

  • Original language name

    On Degree Properties of Crossing-critical Families of Graphs

  • Original language description

    Answering an open question from 2007, we construct infinite k-crossing-critical families of graphs which contain vertices of any prescribed odd degree, for sufficiently large k. From this we derive that, for any set of integers D such that min(D)>=3 and 3,4eD, and for all sufficiently large k there exists a k-crossing-critical family such that the numbers in D are precisely the vertex degrees which occur arbitrarily often in any large enough graph in this family. We also investigate what are the possible average degrees of such crossing-critical families.

  • Czech name

  • Czech description

Classification

  • Type

    D - Article in proceedings

  • CEP classification

    IN - Informatics

  • OECD FORD branch

Result continuities

Others

  • Publication year

    2015

  • Confidentiality

    S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Data specific for result type

  • Article name in the collection

    Graph Drawing and Network Visualization 2015, Lecture Notes in Computer Science 9411

  • ISBN

    9783319272603

  • ISSN

    0302-9743

  • e-ISSN

  • Number of pages

    12

  • Pages from-to

    75-86

  • Publisher name

    Springer Verlag

  • Place of publication

    Berlin

  • Event location

    Los Angeles

  • Event date

    Jan 1, 2015

  • Type of event by nationality

    WRD - Celosvětová akce

  • UT code for WoS article

Result type

D - Article in proceedings

D

CEP

IN - Informatics

Year of implementation

2015