Inserting Multiple Edges into a Planar Graph

J 2023

Inserting Multiple Edges into a Planar Graph

CHIMANI, Markus a Petr HLINĚNÝ

Základní údaje

Originální název

Inserting Multiple Edges into a Planar Graph

Autoři

CHIMANI, Markus (40 Rakousko) a Petr HLINĚNÝ (203 Česká republika, garant, domácí)

Vydání

Journal of Graph Algorithms and Applications, USA, Brown University, 2023, 1526-1719

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Spojené státy

Utajení

není předmětem státního či obchodního tajemství

Odkazy

URL

Kód RIV

RIV/00216224:14330/23:00131118

Organizační jednotka

Fakulta informatiky

DOI

http://dx.doi.org/10.7155/jgaa.00631

Klíčová slova anglicky

crossing number; multiple edge insertion; fixed parameter tractability

Štítky

formela-journal

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 7. 4. 2024 23:05, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

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ávaznosti

GA20-04567S, projekt VaV

Název: Struktura efektivně řešitelných případů těžkých algoritmických problémů na grafech

Investor: Grantová agentura ČR, Structure of tractable instances of hard algorithmic problems on graphs

Citovat

CHIMANI, Markus a Petr HLINĚNÝ. Inserting Multiple Edges into a Planar Graph. Journal of Graph Algorithms and Applications. USA: Brown University, 2023, roč. 27, č. 6, s. 489-522. ISSN 1526-1719. Dostupné z: https://dx.doi.org/10.7155/jgaa.00631.

@article{2294837,
   author = {Chimani, Markus and Hliněný, Petr},
   article_location = {USA},
   article_number = {6},
   doi = {http://dx.doi.org/10.7155/jgaa.00631},
   keywords = {crossing number; multiple edge insertion; fixed parameter tractability},
   language = {eng},
   issn = {1526-1719},
   journal = {Journal of Graph Algorithms and Applications},
   title = {Inserting Multiple Edges into a Planar Graph},
   url = {https://jgaa.info/accepted/2023/631.pdf},
   volume = {27},
   year = {2023}
}

TY  - JOUR
ID  - 2294837
AU  - Chimani, Markus - Hliněný, Petr
PY  - 2023
TI  - Inserting Multiple Edges into a Planar Graph
JF  - Journal of Graph Algorithms and Applications
VL  - 27
IS  - 6
SP  - 489-522
EP  - 489-522
PB  - Brown University
SN  - 15261719
KW  - crossing number
KW  - multiple edge insertion
KW  - fixed parameter tractability
UR  - https://jgaa.info/accepted/2023/631.pdf
N2  - 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.
ER  -

CHIMANI, Markus a Petr HLINĚNÝ. Inserting Multiple Edges into a Planar Graph. \textit{Journal of Graph Algorithms and Applications}. USA: Brown University, 2023, roč.~27, č.~6, s.~489-522. ISSN~1526-1719. Dostupné z: https://dx.doi.org/10.7155/jgaa.00631.

Podrobný výpis o publikaci