New almost-planar crossing-critical graph families

HLINĚNÝ, Petr. New almost-planar crossing-critical graph families. In 6th Slovenian International Conference on Graph Theory. 2007. ISBN 978-961-212-198-3.

Základní údaje

Originální název

New almost-planar crossing-critical graph families

Název česky

Nove temer planarni prusecikove kriticke grafy

Autoři

HLINĚNÝ, Petr ORCID

Vydání

6th Slovenian International Conference on Graph Theory, 2007

---

Další údaje

Jazyk

angličtina

Typ výsledku

Konferenční abstrakt

Obor

10101 Pure mathematics

Stát vydavatele

Slovinsko

Utajení

není předmětem státního či obchodního tajemství

Odkazy

conference

Kód RIV

RIV/00216224:14330/07:00024653

Organizační jednotka

Fakulta informatiky

ISBN

978-961-212-198-3

Klíčová slova anglicky

graph; crossing number; crossing-critical

Štítky

crossing number, crossing-critical, graph

Příznaky

Mezinárodní význam

---

Anotace

V originále

We show that, for all choices of integers $k>2$ and $m$, there are simple $3$-connected $k$-crossing-critical graphs containing more than $m$ vertices of each even degree $\leq2k-2$. This construction answers one half of a question raised by Bokal, while the other half asking analogously about vertices of odd degrees at least $5$ in crossing-critical graphs remains open. Furthermore, our constructed graphs have several other interesting properties; for instance, they are almost planar and their average degree can attain any rational value in the interval $\big[4,6-\frac8{k+1}\big)$.

Česky

Konstuhujeme k-prusecikove kriticke grafy obsahujici libovolne mnoho vrcholu kazdeho sudeho stupne.

---

Návaznosti

GA201/05/0050, projekt VaV

Název: Strukturální vlastnosti a algoritmická složitost diskrétních problémů