BOUNDING AND COMPUTING OBSTACLE NUMBERS OF GRAPHS

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F24%3A10490824" target="_blank" >RIV/00216208:11320/24:10490824 - isvavai.cz</a>

Výsledek na webu

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

DOI - Digital Object Identifier

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

Jazyk výsledku

angličtina

Název v původním jazyce

BOUNDING AND COMPUTING OBSTACLE NUMBERS OF GRAPHS

Popis výsledku v původním jazyce

An obstacle representation of a graph G consists of a set of pairwise disjoint simply connected closed regions and a one-to-one mapping of the vertices of G to points such that two vertices are adjacent in G if and only if the line segment connecting the two corresponding points does not intersect any obstacle. The obstacle number of a graph is the smallest number of obstacles in an obstacle representation of the graph in the plane such that all obstacles are simple polygons. It is known that the obstacle number of each n - vertex graph is O ( n log n ) [M. Balko, J. Cibulka, and P. Valtr, Discrete Comput. Geom ., 59 (2018), pp. 143--164] and that there are n - vertex graphs whose obstacle number is Cl( n/ (log log n ) 2 ) [V. Dujmovic&apos; and P. Morin, Electron. J. Combin ., 22 (2015), 3.1]. We improve this lower bound to Cl( n/ log log n ) for simple polygons and to Cl( n ) for convex polygons. To obtain these stronger bounds, we improve known estimates on the number of n - vertex graphs with bounded obstacle number, solving a conjecture by Dujmovic&apos; and Morin. We also show that if the drawing of some n - vertex graph is given as part of the input, then for some drawings Cl( n 2 ) obstacles are required to turn them into an obstacle representation of the graph. Our bounds are asymptotically tight in several instances. We complement these combinatorial bounds by two complexity results. First, we show that computing the obstacle number of a graph G is fixed -parameter tractable in the vertex cover number of G. Second, we show that, given a graph G and a simple polygon P, it is NP -hard to decide whether G admits an obstacle representation using P as the only obstacle.

Název v anglickém jazyce

BOUNDING AND COMPUTING OBSTACLE NUMBERS OF GRAPHS

Popis výsledku anglicky

An obstacle representation of a graph G consists of a set of pairwise disjoint simply connected closed regions and a one-to-one mapping of the vertices of G to points such that two vertices are adjacent in G if and only if the line segment connecting the two corresponding points does not intersect any obstacle. The obstacle number of a graph is the smallest number of obstacles in an obstacle representation of the graph in the plane such that all obstacles are simple polygons. It is known that the obstacle number of each n - vertex graph is O ( n log n ) [M. Balko, J. Cibulka, and P. Valtr, Discrete Comput. Geom ., 59 (2018), pp. 143--164] and that there are n - vertex graphs whose obstacle number is Cl( n/ (log log n ) 2 ) [V. Dujmovic&apos; and P. Morin, Electron. J. Combin ., 22 (2015), 3.1]. We improve this lower bound to Cl( n/ log log n ) for simple polygons and to Cl( n ) for convex polygons. To obtain these stronger bounds, we improve known estimates on the number of n - vertex graphs with bounded obstacle number, solving a conjecture by Dujmovic&apos; and Morin. We also show that if the drawing of some n - vertex graph is given as part of the input, then for some drawings Cl( n 2 ) obstacles are required to turn them into an obstacle representation of the graph. Our bounds are asymptotically tight in several instances. We complement these combinatorial bounds by two complexity results. First, we show that computing the obstacle number of a graph G is fixed -parameter tractable in the vertex cover number of G. Second, we show that, given a graph G and a simple polygon P, it is NP -hard to decide whether G admits an obstacle representation using P as the only obstacle.

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/GA21-32817S" target="_blank" >GA21-32817S: Algoritmické, strukturální a složitostní aspekty geometrických konfigurací</a><br>

Návaznosti

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

Rok uplatnění

2024

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

1095-7146

Svazek periodika

38

Číslo periodika v rámci svazku

2

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

29

Strana od-do

1537-1565

Kód UT WoS článku

001232147900004

EID výsledku v databázi Scopus

2-s2.0-85195195630