Grid representations and the chromatic number

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F13%3A10190180" target="_blank" >RIV/00216208:11320/13:10190180 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1016/j.comgeo.2013.05.003" target="_blank" >http://dx.doi.org/10.1016/j.comgeo.2013.05.003</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.comgeo.2013.05.003" target="_blank" >10.1016/j.comgeo.2013.05.003</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Grid representations and the chromatic number

Popis výsledku v původním jazyce

A grid drawing of a graph maps vertices to the grid Z(d) and edges to line segments that avoid grid points representing other vertices. We show that a graph G is q(d)-colorable, d, g }= 2, if and only if there is a grid drawing of G in Z(d) in which no line segment intersects more than q grid points. This strengthens the result of D. Flores Penaloza and F.J. Zaragoza Martinez. Second, we study grid drawings with a bounded number of columns, introducing some new NP-complete problems. Finally, we show that any planar graph has a planar grid drawing where every line segment contains exactly two grid points. This result proves conjectures asked by D. Flores Penaloza and F.J. Zaragoza Martinez. (c) 2013 Published by Elsevier B.V.

Název v anglickém jazyce

Grid representations and the chromatic number

Popis výsledku anglicky

A grid drawing of a graph maps vertices to the grid Z(d) and edges to line segments that avoid grid points representing other vertices. We show that a graph G is q(d)-colorable, d, g }= 2, if and only if there is a grid drawing of G in Z(d) in which no line segment intersects more than q grid points. This strengthens the result of D. Flores Penaloza and F.J. Zaragoza Martinez. Second, we study grid drawings with a bounded number of columns, introducing some new NP-complete problems. Finally, we show that any planar graph has a planar grid drawing where every line segment contains exactly two grid points. This result proves conjectures asked by D. Flores Penaloza and F.J. Zaragoza Martinez. (c) 2013 Published by Elsevier B.V.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

<a href="/cs/project/GEGIG%2F11%2FE023" target="_blank" >GEGIG/11/E023: Kreslení grafů a jejich geometrické reprezentace</a><br>

Návaznosti

S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2013

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

Computational Geometry: Theory and Applications

ISSN

0925-7721

e-ISSN

—

Svazek periodika

46

Číslo periodika v rámci svazku

8

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

13

Strana od-do

990-1002

Kód UT WoS článku

000321082000008

EID výsledku v databázi Scopus

—