SUBLINEAR SEPARATORS IN INTERSECTION GRAPHS OF CONVEX SHAPES

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F21%3A10437051" target="_blank" >RIV/00216208:11320/21:10437051 - isvavai.cz</a>

Výsledek na webu

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=8XLxDwODDY" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=8XLxDwODDY</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1137/20M1311156" target="_blank" >10.1137/20M1311156</a>

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

<a href="/cs/project/GA17-04611S" target="_blank" >GA17-04611S: Ramseyovské aspekty barvení grafů</a><br>

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