SUBLINEAR SEPARATORS IN INTERSECTION GRAPHS OF CONVEX SHAPES

Kód výsledku v IS VaVaI

RIV/00216208:11320/21:10437051 - isvavai.cz

Výsledek na webu

https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=8XLxDwODDY

DOI - Digital Object Identifier

10.1137/20M1311156

Jazyk výsledku

angličtina

Název v původním jazyce

SUBLINEAR SEPARATORS IN INTERSECTION GRAPHS OF CONVEX SHAPES

Popis výsledku v původním jazyce

We give a natural sufficient condition for an intersection graph of compact convex sets in R-d to have a balanced separator of sublinear size. This condition generalizes several previous results on sublinear separators in intersection graphs. Furthermore, the argument used to prove the existence of sublinear separators is based on a connection with generalized coloring numbers which has not been previously explored in geometric settings.

Název v anglickém jazyce

SUBLINEAR SEPARATORS IN INTERSECTION GRAPHS OF CONVEX SHAPES

Popis výsledku anglicky

We give a natural sufficient condition for an intersection graph of compact convex sets in R-d to have a balanced separator of sublinear size. This condition generalizes several previous results on sublinear separators in intersection graphs. Furthermore, the argument used to prove the existence of sublinear separators is based on a connection with generalized coloring numbers which has not been previously explored in geometric settings.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

GA17-04611S: Ramseyovské aspekty barvení grafů

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2021

Kód důvěrnosti údajů

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

Název periodika

SIAM Journal on Discrete Mathematics

ISSN

0895-4801

e-ISSN

—

Svazek periodika

35

Číslo periodika v rámci svazku

2

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

16

Strana od-do

1149-1164

Kód UT WoS článku

000674142200026

EID výsledku v databázi Scopus

2-s2.0-85108682562