Inserting Multiple Edges into a Planar Graph

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F23%3A00131118" target="_blank" >RIV/00216224:14330/23:00131118 - isvavai.cz</a>

Výsledek na webu

<a href="https://jgaa.info/accepted/2023/631.pdf" target="_blank" >https://jgaa.info/accepted/2023/631.pdf</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.7155/jgaa.00631" target="_blank" >10.7155/jgaa.00631</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Inserting Multiple Edges into a Planar Graph

Popis výsledku v původním jazyce

Let G be a connected planar (but not yet embedded) graph and F a set of edges with ends in V(G) and not belonging to E(G). The multiple edge insertion problem (MEI) asks for a drawing of G+F with the minimum number of pairwise edge crossings, such that the subdrawing of G is plane. A solution to this problem is known to approximate the crossing number of the graph G+F, but unfortunately, finding an exact solution to MEI is NP-hard for general F. The MEI problem is linear-time solvable for the special case of |F|=1 (SODA 01 and Algorithmica), and there is a polynomial-time solvable extension in which all edges of F are incident to a common vertex which is newly introduced into G (SODA 09). The complexity for general F but with constant k=|F| was open, but algorithms both with relative and absolute approximation guarantees have been presented (SODA 11, ICALP 11 and JoCO). We present a fixed-parameter algorithm for the MEI problem in the case that G is biconnected, which is extended to also cover the case of connected G with cut vertices of bounded degree. These are the first exact algorithms for the general MEI problem, and they run in time O(|V(G)|) for any constant k.

Název v anglickém jazyce

Inserting Multiple Edges into a Planar Graph

Popis výsledku anglicky

Let G be a connected planar (but not yet embedded) graph and F a set of edges with ends in V(G) and not belonging to E(G). The multiple edge insertion problem (MEI) asks for a drawing of G+F with the minimum number of pairwise edge crossings, such that the subdrawing of G is plane. A solution to this problem is known to approximate the crossing number of the graph G+F, but unfortunately, finding an exact solution to MEI is NP-hard for general F. The MEI problem is linear-time solvable for the special case of |F|=1 (SODA 01 and Algorithmica), and there is a polynomial-time solvable extension in which all edges of F are incident to a common vertex which is newly introduced into G (SODA 09). The complexity for general F but with constant k=|F| was open, but algorithms both with relative and absolute approximation guarantees have been presented (SODA 11, ICALP 11 and JoCO). We present a fixed-parameter algorithm for the MEI problem in the case that G is biconnected, which is extended to also cover the case of connected G with cut vertices of bounded degree. These are the first exact algorithms for the general MEI problem, and they run in time O(|V(G)|) for any constant k.

Druh

J_SC - Článek v periodiku v databázi SCOPUS

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/GA20-04567S" target="_blank" >GA20-04567S: Struktura efektivně řešitelných případů těžkých algoritmických problémů na grafech</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2023

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

Journal of Graph Algorithms and Applications

ISSN

1526-1719

e-ISSN

—

Svazek periodika

27

Číslo periodika v rámci svazku

6

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

34

Strana od-do

489-522

Kód UT WoS článku

—

EID výsledku v databázi Scopus

2-s2.0-85165760093