General lower bounds for the minor crossing number of graphs

Drago Bokal (Author), Éva Czabarka (Author), László Székely (Author), Imrich Vrt'o (Author)

Abstract

Obstajajo tri splošne spodnje meje za minorsko prekrižno število grafov: prekrižna lema, metoda z bisekcijo in metoda z vložitvami. V tem prispevku predstavimo njihove prilagoditve za minorsko prekrižno število grafov. S tako pridobljenimi spodnjimi mejami izboljšamo znane rezultate za minorsko prekrižno število hiperkock. Poleg navedenih rezultatov predstavimo tudi povezavo med minorskim prekrižnim številom in grafi, predstavljivimi s krivuljami (string-graphs).

Keywords

teorija grafov;minorsko prekrižno število;grafovski minor;krivuljski grafi;hiper kocke;graph theory;minor crossing number;graph minor;string graphs;hypercubes;

Data

Language:	English
Year of publishing:	2010
Typology:	1.01 - Original Scientific Article
Organization:	UM FNM - Faculty of Natural Sciences and Mathematics
UDC:	519.17
COBISS:	15636057
ISSN:	0179-5376
Views:	29
Downloads:	3
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	Unknown
Secondary title:	Splošne spodnje meje za minorsko prekrižno število grafov
Secondary abstract:	There are three general lower bound techniques for the crossing numbers of graphs: the Crossing Lemma, the bisection method and the embedding method. In this contribution, we present their adaptations to the minor crossing number. Using the adapted bounds, we improve on the known bounds on the minor crossing number of hypercubes. We also point out relations of the minor crossing number to string graphs.
URN:	URN:SI:UM:
Type (COBISS):	Not categorized
Pages:	str. 463-483
Volume:	Vol. 44
Issue:	no. 2
Chronology:	2010
ID:	1475178