Attributes | Values |
---|
rdf:type
| |
Description
| - Crossing minimization is one of the most challenging algorithmic problems in topological graph theory, with strong ties to graph drawing applications. Despite a long history of intensive research, no practical ``good'' algorithm for crossing minimization is known (this is hardly surprising, since the problem itself is NP-complete). Even more surprising is how little we know about a seemingly simple particular pro-blem: to minimize the number of crossings in an {it almost planar} graph, that is, a graph with an edge whose removal leaves a planar graph. This problem is in turn a building block in an edge--insertion heuristic for crossing minimization. We shall give some examples demonstrating that this particular problem is indeed deeply nontrivial. Most remarkably, the important question of its computational complexity remains an open problem.
- Crossing minimization is one of the most challenging algorithmic problems in topological graph theory, with strong ties to graph drawing applications. Despite a long history of intensive research, no practical ``good'' algorithm for crossing minimization is known (this is hardly surprising, since the problem itself is NP-complete). Even more surprising is how little we know about a seemingly simple particular pro-blem: to minimize the number of crossings in an {it almost planar} graph, that is, a graph with an edge whose removal leaves a planar graph. This problem is in turn a building block in an edge--insertion heuristic for crossing minimization. We shall give some examples demonstrating that this particular problem is indeed deeply nontrivial. Most remarkably, the important question of its computational complexity remains an open problem. (en)
- Crossing minimization is one of the most challenging algorithmic problems in topological graph theory, with strong ties to graph drawing applications. Despite a long history of intensive research, no practical ``good'' algorithm for crossing minimization is known (this is hardly surprising, since the problem itself is NP-complete). Even more surprising is how little we know about a seemingly simple particular pro-blem: to minimize the number of crossings in an {it almost planar} graph, that is, a graph with an edge whose removal leaves a planar graph. This problem is in turn a building block in an edge--insertion heuristic for crossing minimization. We shall give some examples demonstrating that this particular problem is indeed deeply nontrivial. Most remarkably, the important question of its computational complexity remains an open problem. (cs)
|
Title
| - Crossing number of almost planar graphs
- Crossing number of almost planar graphs (en)
- Crossing number of almost planar graphs (cs)
|
skos:prefLabel
| - Crossing number of almost planar graphs
- Crossing number of almost planar graphs (en)
- Crossing number of almost planar graphs (cs)
|
skos:notation
| - RIV/61989100:27240/06:00013588!RIV08-AV0-27240___
|
http://linked.open...avai/riv/aktivita
| |
http://linked.open...avai/riv/aktivity
| - P(1ET101940420), P(GA201/05/0050)
|
http://linked.open...vai/riv/dodaniDat
| |
http://linked.open...aciTvurceVysledku
| |
http://linked.open.../riv/druhVysledku
| |
http://linked.open...iv/duvernostUdaju
| |
http://linked.open...titaPredkladatele
| |
http://linked.open...dnocenehoVysledku
| |
http://linked.open...ai/riv/idVysledku
| - RIV/61989100:27240/06:00013588
|
http://linked.open...riv/jazykVysledku
| |
http://linked.open.../riv/klicovaSlova
| |
http://linked.open.../riv/klicoveSlovo
| |
http://linked.open...ontrolniKodProRIV
| |
http://linked.open...v/mistoKonaniAkce
| |
http://linked.open...in/vavai/riv/obor
| |
http://linked.open...ichTvurcuVysledku
| |
http://linked.open...cetTvurcuVysledku
| |
http://linked.open...ocetUcastnikuAkce
| |
http://linked.open...nichUcastnikuAkce
| |
http://linked.open...vavai/riv/projekt
| |
http://linked.open...UplatneniVysledku
| |
http://linked.open...iv/statKonaniAkce
| |
http://linked.open...iv/tvurceVysledku
| - Hliněný, Petr
- Salazar, G.
|
http://linked.open...vavai/riv/typAkce
| |
http://linked.open.../riv/ukonceniAkce
| |
http://linked.open.../riv/zahajeniAkce
| |
http://localhost/t...ganizacniJednotka
| |