Complexity of Anchored Crossing Number and Crossing Number of
Almost Planar Graphs

D 2025

Complexity of Anchored Crossing Number and Crossing Number of Almost Planar Graphs

HLINĚNÝ, Petr

Základní údaje

Originální název

Complexity of Anchored Crossing Number and Crossing Number of Almost Planar Graphs

Autoři

HLINĚNÝ, Petr

Vydání

LIPIcs 345. Germany, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025), od s. "59:1"-"59:17", 17 s. 2025

Nakladatel

Schloss Dagstuhl - Leibniz Center for Informatics

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10200 1.2 Computer and information sciences

Utajení

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

Forma vydání

elektronická verze "online"

Označené pro přenos do RIV

Ano

Kód RIV

RIV/00216224:14330/25:00144000

Organizační jednotka

Fakulta informatiky

ISSN

Klíčová slova anglicky

Crossing number; Anchored drawing; Almost planar graph; NP-hardness

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 2. 6. 2026 17:29, Mgr. Petra Trembecká, Ph.D.

Anotace

V originále

We deal with the problem of computing the exact crossing number of almost planar graphs and the closely related problem of computing the exact anchored crossing number of a pair of planar graphs. It was shown by [Cabello and Mohar, 2013] that both problems are NP-hard; although they required an unbounded number of high-degree vertices (in the first problem) or an unbounded number of anchors (in the second problem) to prove their result. Somehow surprisingly, only three vertices of degree greater than 3 altogether, or only three anchors per each of the two graphs, are sufficient to maintain hardness of these problems, as we prove here. The new result also improves the previous result on hardness of joint crossing number on surfaces by [Hliněný and Salazar, 2015]. Our result is best possible in the anchored case since the anchored crossing number of a pair of planar graphs with two anchors each is trivial, and close to being best possible in the almost planar case since the crossing number is polytime computable for almost planar graphs of maximum degree 3 [Riskin 1996, Cabello and Mohar 2011]. The complexity of crossing number of almost planar graphs with one or two vertices of degree greater than 3 is, interestingly, still wide open.

Citovat

HLINĚNÝ, Petr. Complexity of Anchored Crossing Number and Crossing Number of Almost Planar Graphs. Online. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). LIPIcs 345. Germany: Schloss Dagstuhl - Leibniz Center for Informatics, 2025, s. "59:1"-"59:17", 17 s. ISSN 1868-8969. Dostupné z: https://doi.org/10.4230/LIPIcs.MFCS.2025.59.

@inproceedings{2561537,
   author = {Hliněný, Petr},
   address = {Germany},
   booktitle = {50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
   doi = {https://doi.org/10.4230/LIPIcs.MFCS.2025.59},
   edition = {LIPIcs 345},
   keywords = {Crossing number; Anchored drawing; Almost planar graph; NP-hardness},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {Germany},
   pages = {"59:1"-"59:17"},
   publisher = {Schloss Dagstuhl - Leibniz Center for Informatics},
   title = {Complexity of Anchored Crossing Number and Crossing Number of Almost Planar Graphs},
   year = {2025}
}

TY  - CONF
ID  - 2561537
AU  - Hliněný, Petr
PY  - 2025
TI  - Complexity of Anchored Crossing Number and Crossing Number of Almost Planar Graphs
PB  - Schloss Dagstuhl - Leibniz Center for Informatics
CY  - Germany
KW  - Crossing number
KW  - Anchored drawing
KW  - Almost planar graph
KW  - NP-hardness
N2  - We deal with the problem of computing the exact crossing number of almost planar graphs and the closely related problem of computing the exact anchored crossing number of a pair of planar graphs. It was shown by [Cabello and Mohar, 2013] that both problems are NP-hard; although they required an unbounded number of high-degree vertices (in the first problem) or an unbounded number of anchors (in the second problem) to prove their result. Somehow surprisingly, only three vertices of degree greater than 3 altogether, or only three anchors per each of the two graphs, are sufficient to maintain hardness of these problems, as we prove here. The new result also improves the previous result on hardness of joint crossing number on surfaces by [Hliněný and Salazar, 2015]. Our result is best possible in the anchored case since the anchored crossing number of a pair of planar graphs with two anchors each is trivial, and close to being best possible in the almost planar case since the crossing number is polytime computable for almost planar graphs of maximum degree 3 [Riskin 1996, Cabello and Mohar 2011]. The complexity of crossing number of almost planar graphs with one or two vertices of degree greater than 3 is, interestingly, still wide open.
ER  -

HLINĚNÝ, Petr. Complexity of Anchored Crossing Number and Crossing Number of Almost Planar Graphs. Online. In \textit{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)}. LIPIcs 345. Germany: Schloss Dagstuhl - Leibniz Center for Informatics, 2025, s.~''59:1''-''59:17'', 17 s. ISSN~1868-8969. Dostupné z: https://doi.org/10.4230/LIPIcs.MFCS.2025.59.

Přehled o publikaci