About: Computing the stretch of an embedded graph

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

About: Computing the stretch of an embedded graph 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 graph embedded in an orientable surface Sigma, possibly with edge weights, and denote by len(gamma) the length (the number of edges or the sum of the edge weights) of a cycle. in G. The stretch of a graph embedded on a surface is the minimum of len(alpha) . len(beta) over all pairs of cycles alpha and beta that cross exactly once. We provide two algorithms to compute the stretch of an embedded graph, each based on a different principle. The first algorithm is based on surgery and computes the stretch in time O(g(4)n log n) with high probability, or in time O(g(4)n log(2) n) in the worst case, where g is the genus of the surface S and n is the number of vertices in G. The second algorithm is based on using a short homology basis and computes the stretch in time O(n(2) log n + n(2)g + ng(3)). Let G be a graph embedded in an orientable surface Sigma, possibly with edge weights, and denote by len(gamma) the length (the number of edges or the sum of the edge weights) of a cycle. in G. The stretch of a graph embedded on a surface is the minimum of len(alpha) . len(beta) over all pairs of cycles alpha and beta that cross exactly once. We provide two algorithms to compute the stretch of an embedded graph, each based on a different principle. The first algorithm is based on surgery and computes the stretch in time O(g(4)n log n) with high probability, or in time O(g(4)n log(2) n) in the worst case, where g is the genus of the surface S and n is the number of vertices in G. The second algorithm is based on using a short homology basis and computes the stretch in time O(n(2) log n + n(2)g + ng(3)). (en)
Title	Computing the stretch of an embedded graph Computing the stretch of an embedded graph (en)
skos:prefLabel	Computing the stretch of an embedded graph Computing the stretch of an embedded graph (en)
skos:notation	RIV/00216224:14330/14:00074093!RIV15-GA0-14330___
http://linked.open...avai/riv/aktivita	P
http://linked.open...avai/riv/aktivity	P(GEGIG/11/E023)
http://linked.open...iv/cisloPeriodika	3
http://linked.open...vai/riv/dodaniDat	2015
http://linked.open...aciTvurceVysledku	Hliněný, Petr
http://linked.open.../riv/druhVysledku	J - Článek v odborném periodiku
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	8518
http://linked.open...ai/riv/idVysledku	RIV/00216224:14330/14:00074093
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	topological graph theory; embedded graph; crossings; nonseparating cycle; homology basis (en)
http://linked.open.../riv/klicoveSlovo	crossings embedded graph homology basis nonseparating cycle topological graph theory
http://linked.open...odStatuVydavatele	US - Spojené státy americké
http://linked.open...ontrolniKodProRIV	[693206D54B20]
http://linked.open...i/riv/nazevZdroje	SIAM Journal on Discrete Mathematics
http://linked.open...in/vavai/riv/obor	BA
http://linked.open...ichTvurcuVysledku	1 (xsd:int)
http://linked.open...cetTvurcuVysledku	3 (xsd:int)
http://linked.open...vavai/riv/projekt	Graph Drawings and Representations
http://linked.open...UplatneniVysledku	2014
http://linked.open...v/svazekPeriodika	28
http://linked.open...iv/tvurceVysledku	Chimani, Markus Hliněný, Petr Cabello, Sergio
http://linked.open...ain/vavai/riv/wos	000343230800019
issn	0895-4801
number of pages	11 (xsd:int)
http://bibframe.org/vocab/doi	10.1137/130945636
http://localhost/t...ganizacniJednotka	14330

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