On the Crossing Number of Almost Planar Graphs
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F06%3A00024654" target="_blank" >RIV/00216224:14330/06:00024654 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
On the Crossing Number of Almost Planar Graphs
Original language description
Crossing minimization is one of the most challenging algorithmic problems in topological graph theory, and it has strong ties with graph drawing applications. Despite long history of intensive research, there is still no practical ``good'' algorithm forcrossing minimization known. (The problem itself is $NP$-complete.) It is even surprising how little we know about a seemingly simple particular problem --- to minimize the number of crossings in a planar graph plus one edge, which is a building block ina so-called edge-insertion heuristic for crossing minimization. We shall show few examples demonstrating that this particular problem is indeed deeply nontrivial. Unfortunately, the important question of its computational complexity is left open for future research.
Czech name
Průsečíkové číslo téměř planárních grafů
Czech description
Věnujeme se zdánlivě lehkému a přesto překvapivě obtížnému problému minimalizace průsečíků planárního grafu s jednou hranou navíc. Podáváme aproximační algoritmus.
Classification
Type
O - Miscellaneous
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GA201%2F05%2F0050" target="_blank" >GA201/05/0050: Structural properties and algorithmic complexity of discrete problems</a><br>
Continuities
Z - Vyzkumny zamer (s odkazem do CEZ)
Others
Publication year
2006
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů