**A characterization of horizontal visibility graphs and combinatorics on words.** / Gutin, Gregory; Mansour, T.; Severini, S. .

Research output: Contribution to journal › Article › peer-review

Published

**A characterization of horizontal visibility graphs and combinatorics on words.** / Gutin, Gregory; Mansour, T.; Severini, S. .

Research output: Contribution to journal › Article › peer-review

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.

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.

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.

@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",

}

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 -