Cubic plane graphs on a given point set

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F15%3A10317337" target="_blank" >RIV/00216208:11320/15:10317337 - isvavai.cz</a>

Výsledek na webu

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

DOI - Digital Object Identifier

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

Jazyk výsledku

angličtina

Název v původním jazyce

Cubic plane graphs on a given point set

Popis výsledku v původním jazyce

Let P be a set of n>3 points in the plane that is in general position and such that n is even. We investigate the problem whether there is a (0-, 1- or 2-connected) cubic plane straight-line graph on P. No polynomial-time algorithm is known for this problem. Based on a reduction to the existence of certain diagonals of the boundary cycle of the convex hull of P, we give the first polynomial-time algorithm that checks for 2-connected cubic plane graphs; the algorithm is constructive and runs in time O (n^3). We also show which graph structure can be expected when there is a cubic plane graph on P; e.g., a cubic plane graph on P implies a connected cubic plane graph on P, and a 2-connected cubic plane graph on P implies a 2-connected cubic plane graph onP that contains the boundary cycle of P. We extend the above algorithm to check for arbitrary cubic plane graphs in time O (n^3).

Název v anglickém jazyce

Cubic plane graphs on a given point set

Popis výsledku anglicky

Let P be a set of n>3 points in the plane that is in general position and such that n is even. We investigate the problem whether there is a (0-, 1- or 2-connected) cubic plane straight-line graph on P. No polynomial-time algorithm is known for this problem. Based on a reduction to the existence of certain diagonals of the boundary cycle of the convex hull of P, we give the first polynomial-time algorithm that checks for 2-connected cubic plane graphs; the algorithm is constructive and runs in time O (n^3). We also show which graph structure can be expected when there is a cubic plane graph on P; e.g., a cubic plane graph on P implies a connected cubic plane graph on P, and a 2-connected cubic plane graph on P implies a 2-connected cubic plane graph onP that contains the boundary cycle of P. We extend the above algorithm to check for arbitrary cubic plane graphs in time O (n^3).

Druh

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

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Centrum excelence - Institut teoretické informatiky (CE-ITI)</a><br>

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2015

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

48

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

13

Strana od-do

1-13

Kód UT WoS článku

000342877700001

EID výsledku v databázi Scopus

2-s2.0-84903162265