A simple construction of high representativity triangulations
type: Item
instance of: scholarly article
title: A simple construction of high representativity triangulations
zbMATH Open document ID: 0890.05023
DOI: 10.1016/S0012-365X(96)00132-X
author: Teresa Przytycka
author: Józef H. Przytycki
published in: Discrete Mathematics
publication date: 1998-06-29T00:00:00Z
review text: The representability of a graph embedded in a surface is the length of the shortest noncontractible facial walk. Informally speaking, the concept measures how well the embedding approximates the surface. High representability suggests that the embedding is ``highly locally planar.'' This paper provides polynomial-time constructions of high representability triangulations of compact surfaces. The authors give improvements of the previously known lower bound for the representability of such triangulations. The results are extended to nonorientable surfaces and surfaces with boundary.
reviewed by: M.Marx
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1062450
zbMATH Keywords: representability
zbMATH Keywords: surface
zbMATH Keywords: embedding
zbMATH Keywords: triangulations
MaRDI profile type: Publication
cites work: Densely embedded graphs
cites work: Q3728934
cites work: Q5422499
cites work: Riemannsche Flächen mit großer Kragenweite
cites work: Q5725269
cites work: On Short Noncontractible Cycles in Embedded Graphs
cites work: Q4732110
cites work: On a Lower Bound for Short Noncontractible Cycles in Embedded Graphs
cites work: Q4273852
cites work: Graph minors. VII: Disjoint paths on a surface
cites work: Q3972954
cites work: Embeddings of graphs with no short noncontractible cycles
cites work: Q3942069
full work available at URL: s0012-365x(96)00132-x
OpenAlex ID: W2058761975
description: scientific article; zbMATH DE number 1062450