Unit Bar-Visibility Layouts of Triangulated Polygons

Autor:	Joan P. Hutchinson, Ellen Gethner, Alice M. Dean
Rok vydání:	2005
Předmět:	Discrete mathematics Visibility graph Computer Science::Computational Geometry Planar graph law.invention Combinatorics symbols.namesake law Outerplanar graph Polygon String graph symbols Circle graph Graph factorization Complement graph Mathematics
Zdroj:	Graph Drawing ISBN: 9783540245285 Graph Drawing
DOI:	10.1007/978-3-540-31843-9_13
Popis:	A triangulated polygon is a 2-connected maximal outerplanar graph. A unit bar-visibility graph (UBVG for short) is a graph whose vertices can be represented by disjoint, horizontal, unit-length bars in the plane so that two vertices are adjacent if and only if there is a non-degenerate, unobstructed, vertical band of visibility between the corresponding bars. We give combinatorial and geometric characterizations of the triangulated polygons that are UBVGs. To each triangulated polygon G we assign a character string with the property that G is a UBVG if and only if the string satisfies a certain regular expression. Given a string that satisfies this condition, we describe a linear-time algorithm that uses it to produce a UBV layout of G.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::c7934881da00bfdfe25176b2ad275d50 https://doi.org/10.1007/978-3-540-31843-9_13 Zobrazit plný text záznamu