Polylogarithmic approximation for Euler genus on bounded degree graphs

DOI10.1145/3313276.3316409zbMath1433.68299OpenAlexW2953115480MaRDI QIDQ5212757

Anastasios Sidiropoulos, Ken-ichi Kawarabayashi

Publication date: 30 January 2020

Published in: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3313276.3316409

zbMATH Keywords

crossing numberapproximation algorithmsgraph genus

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (1)

The Degenerate Crossing Number and Higher-Genus Embeddings

This page was built for publication: Polylogarithmic approximation for Euler genus on bounded degree graphs