Generalised disk graphs

Abstract

Generalized Disk Graphs were introduced as a faithful abstraction of wireless interference. In this paper we show how these graphs can be represented geometrically in all dimensions and then use this geometric representation to characterize the graphs and find forbidden subgraphs. We find that in the one dimensional case, we are able to order the vertices which allows us to restrict the structure of subgraphs in relation to the graphs order. We show that the graph $K_{2,3}$ is forbidden in the one-dimensional case. We then relate generalized disc graphs to other known graph classes, give bounds on the chromatic number in one and two dimensions and give exact solutions to the maximum weighted independent set and maximum clique problems in one dimension.

Alhæfð skífunet voru kynnt sem sértekning þráðlausra neta. Í þessari grein munum við sýna hvernig má framsetja þessi net rúmfræðilega í öllum víddum. Við notum svo þessa rúmfræðilegu framsetningu til að finna sértæka eiginleika þessara neta eins og að finna óleyfileg hlutnet. Við sýnum að þegar við takmörkum netin við eina vídd að þá getum við raðað hnútunum á þannig máta að við getum fundið takmarkandi mynstur hlutneta í tengsl við þessa röðun. Við sýnum að netið $K_{2,3}$ er ekki Alhæft skífunet í einni vídd, né nokkur leggjahlutun þess. Við finnum svo vensl við aðra netaflokka, finnum skorður á litatölu netanna í einni og tveimur víddum og leysum vandamál eins og að finna stærsta óháða mengið og stærsta tengda hlutnetið á skilvirkan hátt þegar netin eru takmörkuð við eina vídd.