Moving vertices to make drawings plane

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F08%3A00101162" target="_blank" >RIV/00216208:11320/08:00101162 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

Moving vertices to make drawings plane

Original language description

First, we show that MINMOVED-VERTICES is NP-hard and hard to approximate. Second, we establish a connection to the graph-drawing problem 1BENDPOINTSETEMBED-DABILITY, which yields similar results for that problem. Third, we give bounds for the behavior ofMINMOVED VERTICES on trees and general planar graphs.

Czech name

Planarizace nakreslených grafů hýbáním vrcholy

Czech description

Ukazujeme, že určit minimální počet vrcholů, jejichž vhodným přesunutím je možno dané nakreslení grafu planarizovat, je NP-těžké a je těžké i aproximovat. Podobný výsledek ukazujeme pro příbuznou úlohu kreslení grafů s nejvýše jedním ohybem na každé hraně. Nakonec podáváme odhady pro minimální počet planarizujících vrcholů pro stromy a obecné rovinné grafy.

Type

D - Article in proceedings

CEP classification

BA - General mathematics

OECD FORD branch

—

Project

<a href="/en/project/1M0545" target="_blank" >1M0545: Institute for Theoretical Computer Science</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year

2008

Confidentiality

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

Article name in the collection

GRAPH DRAWING 2007

ISBN

978-3-540-77536-2

ISSN

—

e-ISSN

—

Number of pages

12

Pages from-to

—

Publisher name

Springer

Place of publication

Berlin

Event location

Berlin

Event date

Jan 1, 2008

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

000253367700011