A characterization of horizontal visibility graphs and combinatorics on words. / Gutin, Gregory; Mansour, T.; Severini, S. .
In: Physica A: Statistical Mechanics and its Applications , Vol. 390, 2011, p. 2421-2428.Research output: Contribution to journal › Article › peer-review
Standard
A characterization of horizontal visibility graphs and combinatorics on words. / Gutin, Gregory; Mansour, T.; Severini, S. .
In: Physica A: Statistical Mechanics and its Applications , Vol. 390, 2011, p. 2421-2428.Research output: Contribution to journal › Article › peer-review
Harvard
APA
Vancouver
Author
BibTeX
}
RIS
TY - JOUR
T1 - A characterization of horizontal visibility graphs and combinatorics on words
AU - Gutin, Gregory
AU - Mansour, T.
AU - Severini, S.
PY - 2011
Y1 - 2011
N2 - An Horizontal Visibility Graph (for short, HVG) is defined in association withan ordered set of non-negative reals. HVGs realize a methodology in theanalysis of time series, their degree distribution being a good discriminatorbetween randomness and chaos [B. Luque, \emph{et al.}, \emph{Phys. Rev. E}\textbf{80} (2009), 046103]. We prove that a graph is an HVG if and only ifouterplanar and has a Hamilton path. Therefore, an HVG is a noncrossing graph,as defined in algebraic combinatorics [P. Flajolet and M. Noy, \emph{DiscreteMath.}, \textbf{204} (1999) 203-229]. Our characterization of HVGs implies alinear time recognition algorithm.\textbf{ }Treating ordered sets as words, wecharacterize subfamilies of HVGs highlighting various connections withcombinatorial statistics and introducing the notion of a visible pair. Withthis technique we determine asymptotically the average number of edges of HVGs.
AB - An Horizontal Visibility Graph (for short, HVG) is defined in association withan ordered set of non-negative reals. HVGs realize a methodology in theanalysis of time series, their degree distribution being a good discriminatorbetween randomness and chaos [B. Luque, \emph{et al.}, \emph{Phys. Rev. E}\textbf{80} (2009), 046103]. We prove that a graph is an HVG if and only ifouterplanar and has a Hamilton path. Therefore, an HVG is a noncrossing graph,as defined in algebraic combinatorics [P. Flajolet and M. Noy, \emph{DiscreteMath.}, \textbf{204} (1999) 203-229]. Our characterization of HVGs implies alinear time recognition algorithm.\textbf{ }Treating ordered sets as words, wecharacterize subfamilies of HVGs highlighting various connections withcombinatorial statistics and introducing the notion of a visible pair. Withthis technique we determine asymptotically the average number of edges of HVGs.
M3 - Article
VL - 390
SP - 2421
EP - 2428
JO - Physica A: Statistical Mechanics and its Applications
JF - Physica A: Statistical Mechanics and its Applications
SN - 0378-4371
ER -