A simple construction of high representativity triangulations

DOI10.1016/S0012-365X(96)00132-XMaRDI QIDQ1367040zbMATH OpenOpenAlexFDO

Authors Teresa Przytycka, Józef H. Przytycki

Publication date 29 June 1998

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(96)00132-x

zbMATH Keywords

embeddingrepresentabilitysurfacetriangulations

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

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.

Recommendations

• scientific article; zbMATH DE number 475596
• scientific article; zbMATH DE number 16301
• Nonhamiltonian triangulations with large connectivity and representativity

Cites work

• A simple construction of high representativity triangulations
• Densely embedded graphs
• Embeddings of graphs with no short noncontractible cycles
• Graph minors. VII: Disjoint paths on a surface
• Graph theory
• scientific article; zbMATH DE number 3961650 (Why is no real title available?)
• scientific article; zbMATH DE number 3759178 (Why is no real title available?)
• scientific article; zbMATH DE number 16301 (Why is no real title available?)
• scientific article; zbMATH DE number 475596 (Why is no real title available?)
• scientific article; zbMATH DE number 4117852 (Why is no real title available?)
• scientific article; zbMATH DE number 3189017 (Why is no real title available?)
• On a Lower Bound for Short Noncontractible Cycles in Embedded Graphs
• On Short Noncontractible Cycles in Embedded Graphs
• Riemannsche Flächen mit großer Kragenweite

Cited in

(7)

• A simple construction of high representativity triangulations
• Nonhamiltonian triangulations with large connectivity and representativity
• Face-width of embedded graphs
• scientific article; zbMATH DE number 16301 (Why is no real title available?)
• scientific article; zbMATH DE number 475596 (Why is no real title available?)
• Polygon representations of surface graphs
• Densely embedded graphs

This page was built for publication: A simple construction of high representativity triangulations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1367040)