About: A Tighter Insertion-based Approximation of the Crossing Number

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

About: A Tighter Insertion-based Approximation of the Crossing Number 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	Let $G$ be a planar graph and $F$ a set of additional edges not yet in $G$. The {\em 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. As an exact solution to MEI is NP-hard for general $F$, we present the first approximation algorithm for MEI which achieves an additive approximation factor (depending only on the size of $F$ and the maximum degree of $G$) in the case of connected~$G$. Our algorithm seems to be the first directly implementable one in that realm, too, next to the single edge insertion. It is also known that an (even approximate) solution to the MEI problem would approximate the crossing number of the \emph{$F$-almost-planar graph} $G+F$, while computing the crossing number of $G+F$ exactly is NP-hard already when $\|F\|=1$. Let $G$ be a planar graph and $F$ a set of additional edges not yet in $G$. The {\em 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. As an exact solution to MEI is NP-hard for general $F$, we present the first approximation algorithm for MEI which achieves an additive approximation factor (depending only on the size of $F$ and the maximum degree of $G$) in the case of connected~$G$. Our algorithm seems to be the first directly implementable one in that realm, too, next to the single edge insertion. It is also known that an (even approximate) solution to the MEI problem would approximate the crossing number of the \emph{$F$-almost-planar graph} $G+F$, while computing the crossing number of $G+F$ exactly is NP-hard already when $\|F\|=1$. (en)
Title	A Tighter Insertion-based Approximation of the Crossing Number A Tighter Insertion-based Approximation of the Crossing Number (en)
skos:prefLabel	A Tighter Insertion-based Approximation of the Crossing Number A Tighter Insertion-based Approximation of the Crossing Number (en)
skos:notation	RIV/00216224:14330/11:00049979!RIV12-GA0-14330___
http://linked.open...avai/predkladatel	Fakulta informatiky
http://linked.open...avai/riv/aktivita	P S Z
http://linked.open...avai/riv/aktivity	P(GAP202/11/0196), P(GEGIG/11/E023), S, Z(MSM0021622419)
http://linked.open...vai/riv/dodaniDat	2012
http://linked.open...aciTvurceVysledku	Hliněný, Petr
http://linked.open.../riv/druhVysledku	D - Článek ve sborníku
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	Masarykova univerzita / Fakulta informatiky
http://linked.open...dnocenehoVysledku	184224
http://linked.open...ai/riv/idVysledku	RIV/00216224:14330/11:00049979
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	crossing number; crossing minimization; planar insertion (en)
http://linked.open.../riv/klicoveSlovo	crossing minimization crossing number planar insertion
http://linked.open...ontrolniKodProRIV	[4567A34C90A6]
http://linked.open...v/mistoKonaniAkce	Zurich, Switzerland
http://linked.open...i/riv/mistoVydani	Gremany
http://linked.open...i/riv/nazevZdroje	Automata, Languages and Programming 38th International Colloquium, ICALP 2011
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...vavai/riv/projekt	Well-structured combinatorial classes, width parameters, and design of efficient algorithms Graph Drawings and Representations
http://linked.open...UplatneniVysledku	2011
http://linked.open...iv/tvurceVysledku	Chimani, Markus Hliněný, Petr
http://linked.open...vavai/riv/typAkce	WRD - Světová
http://linked.open.../riv/zahajeniAkce	2011-01-01 (xsd:date)
http://linked.open...n/vavai/riv/zamer	Highly Parallel and Distributed Computing Systems
number of pages	13 (xsd:int)
http://bibframe.org/vocab/doi	10.1007/978-3-642-22006-7_11
http://purl.org/ne...btex#hasPublisher	Springer-Verlag
https://schema.org/isbn	978-3-642-22005-0
http://localhost/t...ganizacniJednotka	14330
is http://linked.open...avai/riv/vysledek of	A Tighter Insertion-based Approximation of the Crossing Number A Tighter Insertion-based Approximation of the Crossing Number

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