Polylogarithmic approximation for Euler genus on bounded degree graphs

DOI10.1145/3313276.3316409MaRDI QIDQ5212757zbMATH OpenOpenAlexFDO

Authors Ken-ichi Kawarabayashi, Anastasios Sidiropoulos

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

approximation algorithmscrossing numbergraph genus

Mathematics Subject Classification ID

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

Recommendations

• Approximation algorithms for Euler genus and related problems
• Beyond the Euler characteristic: approximating the genus of general graphs (extended abstract)
• A note on approximating graph genus
• Planar crossing numbers of graphs of bounded genus
• An algorithm for the graph crossing number problem

Cited in

(7)

• A note on approximating graph genus
• Beyond the Euler characteristic: approximating the genus of general graphs (extended abstract)
• Approximation algorithms for Euler genus and related problems
• The degenerate crossing number and higher-genus embeddings
• The polynomial randomized algorithm to compute bounded degree graph for TSP based on frequency quadrilaterals
• Lossy planarization: a constant-factor approximate kernelization for planar vertex deletion
• Approximating the crossing number of dense graphs (poster abstract)

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

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