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 journalArticlepeer-review

Published

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 journalArticlepeer-review

Harvard

Gutin, G, Mansour, T & Severini, S 2011, 'A characterization of horizontal visibility graphs and combinatorics on words', Physica A: Statistical Mechanics and its Applications , vol. 390, pp. 2421-2428.

APA

Gutin, G., Mansour, T., & Severini, S. (2011). A characterization of horizontal visibility graphs and combinatorics on words. Physica A: Statistical Mechanics and its Applications , 390, 2421-2428.

Vancouver

Gutin G, Mansour T, Severini S. A characterization of horizontal visibility graphs and combinatorics on words. Physica A: Statistical Mechanics and its Applications . 2011;390:2421-2428.

Author

Gutin, Gregory ; Mansour, T. ; Severini, S. . / A characterization of horizontal visibility graphs and combinatorics on words. In: Physica A: Statistical Mechanics and its Applications . 2011 ; Vol. 390. pp. 2421-2428.

BibTeX

@article{2edde21cc0c34af5adeb56ae4632af1b,
title = "A characterization of horizontal visibility graphs and combinatorics on words",
abstract = "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.",
author = "Gregory Gutin and T. Mansour and S. Severini",
year = "2011",
language = "English",
volume = "390",
pages = "2421--2428",
journal = "Physica A: Statistical Mechanics and its Applications ",
issn = "0378-4371",
publisher = "Elsevier",

}

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 -