COMPUTING THE STRETCH OF AN EMBEDDED GRAPH

DC FieldValueLanguage
dc.contributor.authorCabello, Sergio
dc.contributor.authorChimani, Markus
dc.contributor.authorHlineny, Petr
dc.date.accessioned2021-12-23T16:14:26Z-
dc.date.available2021-12-23T16:14:26Z-
dc.date.issued2014
dc.identifier.issn08954801
dc.identifier.urihttps://osnascholar.ub.uni-osnabrueck.de/handle/unios/11070-
dc.description.abstractLet 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)).
dc.description.sponsorshipSlovenian Research AgencySlovenian Research Agency - Slovenia [P1-0297, J1-4106, L7-5459]; EUROCORES Programme EUROGIGA (project GReGAS) of the European Science Foundation; Carl-Zeiss Foundation; EUROCORES Programme EUROGIGA (project GraDR) of the European Science Foundation; EUROCORES Programme EUROGIGA (project GraDR) of the European Science Foundation, under Czech Science Foundation [GIG/11/E023]; This author's research was supported by the Slovenian Research Agency, program P1-0297, projects J1-4106 and L7-5459, and within the EUROCORES Programme EUROGIGA (project GReGAS) of the European Science Foundation.; This author's research was partially conducted while being funded by a Carl-Zeiss Foundation junior professorship, and also partially supported by EUROCORES Programme EUROGIGA (project GraDR) of the European Science Foundation.; This author's research was supported by EUROCORES Programme EUROGIGA (project GraDR) of the European Science Foundation, under Czech Science Foundation GIG/11/E023.
dc.language.isoen
dc.publisherSIAM PUBLICATIONS
dc.relation.ispartofSIAM JOURNAL ON DISCRETE MATHEMATICS
dc.subjectcrossings
dc.subjectembedded graph
dc.subjecthomology basis
dc.subjectMathematics
dc.subjectMathematics, Applied
dc.subjectnonseparating cycle
dc.subjectPLANAR CROSSING NUMBERS
dc.subjectSURFACE
dc.subjecttopological graph theory
dc.titleCOMPUTING THE STRETCH OF AN EMBEDDED GRAPH
dc.typejournal article
dc.identifier.doi10.1137/130945636
dc.identifier.isiISI:000343230800019
dc.description.volume28
dc.description.issue3
dc.description.startpage1391
dc.description.endpage1401
dc.contributor.orcid0000-0003-2125-1514
dc.contributor.orcid0000-0002-3183-4126
dc.contributor.researcheridF-1127-2011
dc.identifier.eissn10957146
dc.publisher.place3600 UNIV CITY SCIENCE CENTER, PHILADELPHIA, PA 19104-2688 USA
dcterms.isPartOf.abbreviationSIAM Discret. Math.
dcterms.oaStatusGreen Published, Green Submitted
crisitem.author.orcid0000-0002-4681-5550-
crisitem.author.netidChMa572-
Show simple item record

Page view(s)

5
Last Week
0
Last month
0
checked on May 27, 2024

Google ScholarTM

Check

Altmetric