About: Crossing number of almost planar graphs

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Crossing number of almost planar graphs Goto Sponge NotDistinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
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	P
http://linked.open...avai/riv/aktivity	P(1ET101940420), P(GA201/05/0050)
http://linked.open...vai/riv/dodaniDat	2008
http://linked.open...aciTvurceVysledku	Hliněný, Petr
http://linked.open.../riv/druhVysledku	M - Uspořádání (zorganizování) konference
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	Vysoká škola báňská - Technická univerzita Ostrava / Fakulta elektrotechniky a informatiky
http://linked.open...dnocenehoVysledku	470033
http://linked.open...ai/riv/idVysledku	RIV/61989100:27240/06:00013588
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	crossing number (en)
http://linked.open.../riv/klicoveSlovo	crossing number
http://linked.open...ontrolniKodProRIV	[129954BDCDF0]
http://linked.open...v/mistoKonaniAkce	Canada
http://linked.open...in/vavai/riv/obor	IN
http://linked.open...ichTvurcuVysledku	1 (xsd:int)
http://linked.open...cetTvurcuVysledku	2 (xsd:int)
http://linked.open...ocetUcastnikuAkce	37 (xsd:int)
http://linked.open...nichUcastnikuAkce	35 (xsd:int)
http://linked.open...vavai/riv/projekt	Logic and Artificial Intelligence in the area of Multiagent Systems Structural properties and algorithmic complexity of discrete problems
http://linked.open...UplatneniVysledku	2006
http://linked.open...iv/statKonaniAkce	CA - Kanada
http://linked.open...iv/tvurceVysledku	Hliněný, Petr Salazar, G.
http://linked.open...vavai/riv/typAkce	WRD - Světová
http://linked.open.../riv/ukonceniAkce	2007-01-19 (xsd:date)
http://linked.open.../riv/zahajeniAkce	2007-01-14 (xsd:date)
http://localhost/t...ganizacniJednotka	27240

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 58 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software