Další formáty:
BibTeX
LaTeX
RIS
@article{1206003,
author = {Cabello, Sergio and Chimani, Markus and Hliněný, Petr},
article_location = {Philadelphia},
article_number = {3},
doi = {http://dx.doi.org/10.1137/130945636},
keywords = {topological graph theory; embedded graph; crossings; nonseparating cycle; homology basis},
language = {eng},
issn = {0895-4801},
journal = {SIAM Journal on Discrete Mathematics},
title = {Computing the stretch of an embedded graph},
volume = {28},
year = {2014}
}
TY - JOUR
ID - 1206003
AU - Cabello, Sergio - Chimani, Markus - Hliněný, Petr
PY - 2014
TI - Computing the stretch of an embedded graph
JF - SIAM Journal on Discrete Mathematics
VL - 28
IS - 3
SP - 1391-1401
EP - 1391-1401
PB - SIAM
SN - 08954801
KW - topological graph theory
KW - embedded graph
KW - crossings
KW - nonseparating cycle
KW - homology basis
N2 - 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)).
ER -
CABELLO, Sergio, Markus CHIMANI a Petr HLINĚNÝ. Computing the stretch of an embedded graph. \textit{SIAM Journal on Discrete Mathematics}. Philadelphia: SIAM, 2014, roč.~28, č.~3, s.~1391-1401. ISSN~0895-4801. Dostupné z: https://dx.doi.org/10.1137/130945636.
|
